HDU 2665 Kth Number：主席樹 (持久化線段樹) 模板詳解

問題描述

給定長度 N 的數列，回答 Q 個查詢：區間 [l, r] 中第 k 小的數是多少？N, Q 可達 10^5，需離線或線上高效解決。

核心思想：主席樹

主席樹是持久化線段樹的一種，針對「區間第 k 小」問題。基本思路：

1. 將原數組值離散化（排序去重），映射到 1..M。
2. 構建前綴版本線段樹：root[i] 表示前 i 個元素插入後的線段樹。每次插入只新建 O(log M) 個節點，其餘共享。
3. 查詢時，用 root[r] 減去 root[l-1] 得到區間 [l, r] 的頻率統計樹，在上面二分查找第 k 小。

關鍵操作

離散化

vector vals(a+1, a+n+1);
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
int get_id(int x) { return lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1; }

建樹與更新

struct Node { int lson, rson, sum; } tree[MAXN * 20];
int tot = 0;

int build(int l, int r) {
    int id = ++tot;
    tree[id].sum = 0;
    if (l < r) {
        int mid = (l + r) >> 1;
        tree[id].lson = build(l, mid);
        tree[id].rson = build(mid+1, r);
    }
    return id;
}

int update(int pre, int l, int r, int val) {
    int id = ++tot;
    tree[id] = tree[pre];
    tree[id].sum++;
    if (l < r) {
        int mid = (l + r) >> 1;
        if (val <= mid) tree[id].lson = update(tree[pre].lson, l, mid, val);
        else tree[id].rson = update(tree[pre].rson, mid+1, r, val);
    }
    return id;
}

查詢第 k 小

int query(int u, int v, int l, int r, int k) { // u=root[l-1], v=root[r]
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int cnt = tree[tree[v].lson].sum - tree[tree[u].lson].sum;
    if (cnt >= k) return query(tree[u].lson, tree[v].lson, l, mid, k);
    else return query(tree[u].rson, tree[v].rson, mid+1, r, k - cnt);
}

完整流程

1. 讀入 N, Q，數組 a[1..N]。
2. 離散化得 vals[]。
3. root[0] = build(1, M)。
4. for i=1..N: root[i] = update(root[i-1], 1, M, get_id(a[i]))。
5. 每查詢 l, r, k: id = query(root[l-1], root[r], 1, M, k)，輸出 vals[id-1]。

複雜度

• 時間：建樹 O(N log N)，查詢 O(log N)。
• 空間：O(N log N) 節點（約 20N）。

參考程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
const int MAXNODE = MAXN * 20;

struct Node { int l, r, sum; } tr[MAXNODE];
int rt[MAXN], a[MAXN], tot;
vector hs;

int build(int l, int r) {
    int p = ++tot; tr[p].sum = 0;
    if (l < r) {
        int mid = (l+r)>>1;
        tr[p].l = build(l, mid);
        tr[p].r = build(mid+1, r);
    }
    return p;
}

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

int query(int u, int v, int l, int r, int k) {
    if (l == r) return l;
    int mid = (l+r)>>1;
    int cnt = tr[tr[v].l].sum - tr[tr[u].l].sum;
    if (cnt >= k) return query(tr[u].l, tr[v].l, l, mid, k);
    return query(tr[u].r, tr[v].r, mid+1, r, k-cnt);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n, q; cin >> n >> q;
        hs.clear(); tot = 0;
        for (int i=1;i<=n;i++) { cin>>a[i]; hs.push_back(a[i]); }
        sort(hs.begin(), hs.end());
        hs.erase(unique(hs.begin(), hs.end()), hs.end());
        rt[0] = build(1, hs.size());
        for (int i=1;i<=n;i++) {
            int id = lower_bound(hs.begin(), hs.end(), a[i]) - hs.begin() + 1;
            rt[i] = update(rt[i-1], 1, hs.size(), id);
        }
        while (q--) {
            int l, r, k; cin >> l >> r >> k;
            int id = query(rt[l-1], rt[r], 1, hs.size(), k);
            cout << hs[id-1] << '\n';
        }
    }
    return 0;
}