BZOJ 1803 / SPOJ QTREE3：主席樹（可持久化線段樹）查詢樹上第 k 大

問題描述

給定一棵 n 個節點的樹，每個節點有權值。多次查詢：子樹 x 內第 k 大的權值（或節點 id）。

解法：DFS 序 + 主席樹

1. DFS 求每個節點的進入時間 in[x] 和退出時間 out[x]。子樹 x 對應 DFS 序區間 [in[x], out[x]]（每個節點出現兩次，故區間長度為 2×子樹大小）。
2. 按 DFS 序構建主席樹（可持久化線段樹），版本 root[i] 表示前 i 個 DFS 序位置插入的權值多重集。
3. 查詢子樹 x 第 k 大：用 root[out[x]] - root[in[x]-1] 兩棵線段樹相減，在權值域上二分查找第 2k 小（因每個節點出現兩次）。

關鍵細節

• 權值離散化：將所有權值排序去重，建立映射。
• 主席樹節點：left, right, sum。插入時創建 O(log N) 新節點。
• 空間：O(N log N)，N=20000 時約 400 萬節點，需開大數組或內存池。

代碼實現（C++）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int LOG = 18; // log2(200000) < 18

struct Node { int l, r, sum; } tr[MAXN * LOG];
int rt[MAXN], tot = 0;
int n, m, val[MAXN], dfn[MAXN*2], in[MAXN], out[MAXN], dfs_clk = 0;
vector<int> G[MAXN];
vector<int> sorted_val;

int build(int l, int r) { return 0; } // 空節點為 0，sum=0

int update(int prev, int l, int r, int pos) {
    int cur = ++tot;
    tr[cur] = tr[prev];
    tr[cur].sum++;
    if (l == r) return cur;
    int mid = (l + r) >> 1;
    if (pos <= mid) tr[cur].l = update(tr[prev].l, l, mid, pos);
    else tr[cur].r = update(tr[prev].r, mid+1, r, pos);
    return cur;
}

int query(int u, int v, int l, int r, int k) { // v 是新版本, u 是舊版本
    if (l == r) return l;
    int cnt = tr[tr[v].l].sum - tr[tr[u].l].sum;
    int mid = (l + r) >> 1;
    if (k <= cnt) return query(tr[u].l, tr[v].l, l, mid, k);
    else return query(tr[u].r, tr[v].r, mid+1, r, k - cnt);
}

void dfs(int u, int fa) {
    in[u] = ++dfs_clk; dfn[dfs_clk] = u;
    for (int v : G[u]) if (v != fa) dfs(v, u);
    out[u] = ++dfs_clk; dfn[dfs_clk] = u;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val[i]);
        sorted_val.push_back(val[i]);
    }
    sort(sorted_val.begin(), sorted_val.end());
    sorted_val.erase(unique(sorted_val.begin(), sorted_val.end()), sorted_val.end());
    int V = sorted_val.size();

    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].push_back(v); G[v].push_back(u);
    }
    dfs(1, 0);
    rt[0] = 0;
    for (int i = 1; i <= dfs_clk; ++i) {
        int pos = lower_bound(sorted_val.begin(), sorted_val.end(), val[dfn[i]]) - sorted_val.begin() + 1;
        rt[i] = update(rt[i-1], 1, V, pos);
    }
    scanf("%d", &m);
    while (m--) {
        int x, k; scanf("%d%d", &x, &k);
        k *= 2; // 每個節點在 dfn 中出現兩次
        int idx = query(rt[in[x]-1], rt[out[x]], 1, V, k);
        printf("%d\n", sorted_val[idx-1]); // 輸出原始權值
    }
    return 0;
}

複雜度

構建 O(N log N)，單次查詢 O(log N)，空間 O(N log N)。