POJ 2104 K-th Number：主席樹（可持久化線段樹）完整教程與模板

問題描述

給定長度 n ≤ 100,000 的互不相同整數數組，回答 m ≤ 5,000 個查詢：區間 [l, r] 中第 k 小的數是多少？

核心思路：主席樹 = 前綴版本線段樹

• 將數值域離散化為 [1..m]（m ≤ n）。
• 構建 n+1 棵線段樹版本：root[i] 表示前綴 a[1..i] 的頻率統計樹。
• root[i] 由 root[i-1] 經過 O(log n) 節點新建/復用得到（可持久化）。
• 查詢 [l, r] 第 k 小：用 root[r] 減去 root[l-1]，在差值樹上二分尋找第 k 個 1。

關鍵數據結構

const int MAXN = 100000;
const int MAXM = MAXN * 20;  // 每次插入新建 logN 個節點，20 足夠

int lc[MAXM], rc[MAXM], sum[MAXM];  // 左右孩子、區間和
int roots[MAXN + 1];                // 版本根節點
int tot = 0;                        // 節點池指針
int sorted[MAXN + 1];               // 離散化後有序數組

三大核心操作

1. 建立空樹 build(1, m)

int build(int L, int R) {
    int id = ++tot;
    sum[id] = 0;
    if (L < R) {
        int mid = (L + R) >> 1;
        lc[id] = build(L, mid);
        rc[id] = build(mid+1, R);
    }
    return id;
}

2. 單點更新（持久化）update(pre, L, R, pos, val)

int update(int pre, int L, int R, int pos, int val) {
    int cur = ++tot;
    lc[cur] = lc[pre];
    rc[cur] = rc[pre];
    sum[cur] = sum[pre] + val;
    if (L < R) {
        int mid = (L + R) >> 1;
        if (pos <= mid)
            lc[cur] = update(lc[pre], L, mid, pos, val);
        else
            rc[cur] = update(rc[pre], mid+1, R, pos, val);
    }
    return cur;
}

只在訪問路徑上新建節點（log n 個），其餘指向舊版本，實現共享。

3. 區間第 k 小查詢 query(u, v, L, R, k)

int query(int u, int v, int L, int R, int k) {
    if (L == R) return L;
    int mid = (L + R) >> 1;
    int leftSum = sum[lc[v]] - sum[lc[u]];  // [l,r] 左半部計數
    if (k <= leftSum)
        return query(lc[u], lc[v], L, mid, k);
    else
        return query(rc[u], rc[v], mid+1, R, k - leftSum);
}

u = root[l-1], v = root[r]。左子樹計數差即為區間左半部元素個數。

完整主流程

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    while (cin >> n >> q) {
        tot = 0;
        vector<int> a(n+1), vals(n+1);
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            vals[i] = a[i];
        }
        // 離散化
        sort(vals.begin()+1, vals.begin()+n+1);
        int m = unique(vals.begin()+1, vals.begin()+n+1) - vals.begin() - 1;

        // 建空樹版本 0
        roots[n+1] = build(1, m);
        // 從右向左構建前綴版本（或從左向右，查詢時調整 u/v）
        for (int i = n; i >= 1; --i) {
            int pos = lower_bound(vals.begin()+1, vals.begin()+m+1, a[i]) - vals.begin();
            roots[i] = update(roots[i+1], 1, m, pos, 1);
        }

        while (q--) {
            int l, r, k;
            cin >> l >> r >> k;
            int idx = query(roots[l], roots[r+1], 1, m, k);
            cout << vals[idx] << '\n';
        }
    }
    return 0;
}

複雜度分析

常見坑點

1. 離散化去重：unique 返回尾後迭代器，長度計算別漏 -1。
2. 版本方向：代碼採用 root[i] 表示 [i..n] 後綴，查詢用 root[l] 和 root[r+1]。若構建前綴 [1..i]，查詢用 root[l-1] 和 root[r]。統一約定即可。
3. 節點池大小：MAXN * 20 針對 n=1e5, log2(1e5)≈17，20 留有餘量。
4. 輸入輸出優化：題目提示大數據，必須用 scanf/printf 或 ios::sync_with_stdio(false); cin.tie(nullptr);。

主席樹 vs 其他方案

總結

主席樹是解決靜態區間第 k 小問題的標準利器，核心是**可持久化線段樹**實現版本共享。本文提供了從離散化、建樹、更新、查詢到完整主程序的標準模板，配合 lower_bound 离散化與 unique 去重，可直接應用於 POJ 2104、洛谷 P3834 等模板題。理解其「版本樹 = 前綴頻率統計」的本質，能舉一反三解決區間眾數、區間中位數、區間異或第 k 小等變體問題。

1. 上一篇文章： ZOJ 3675 Trim the Nails：指甲刀修剪最小次數 DFS + 剪枝
2. 下一篇文章： ZOJ 3671 Japanese Mahjong III：七對子與十三幺判定算法詳解

C++ 入門

C++11 unique_ptr 詳解：獨佔所有權、移動語意與容器應用

C++11 unique_ptr 詳解：獨佔所有權、移動語意

C/C++ 程式設計新手常見錯誤語錄

如同學習數學、英文需整理錯題集，程式設計師也應總結常見錯誤。

LeetCode 124 - Binary Tree Maximum Path Sum：任意路徑最大和

問題定義 給定二叉樹，路徑定義為任意節點序列，相鄰節點有父子

Codeforces 234A Inna and Choose Options 題解：枚舉矩陣尺寸檢查全 X 列

Codeforces 234A Inna and Choos