POJ 2104 K-th Number：劃分樹（主席樹前身）區間第 K 大查詢

題目簡介

給定長度 n ≤ 100,000 的數組，回答 m ≤ 5,000 個查詢：區間 [i, j] 中第 k 大的數是多少。

解題思路：劃分樹

基於快速排序構建：

1. 對原數組排序得 sorted[]。
2. 遞歸構建：當前區間 [l, r]，中位值 midVal = sorted[(l+r)/2]。將原數組中 ≤ midVal 的放左子樹，> midVal 的放右子樹。記錄 toLeft[depth][i] 表示前 i 個元素中有多少進入左子樹。
3. 查詢：在深度 d，區間 [L, R] 對應樹節點 [l, r]。左子樹數量 s = toLeft[d][R] - toLeft[d][L-1]。若 k ≤ s，遞歸左子樹，新區間 [l + toLeft[d][L-1], l + toLeft[d][R] - 1]；否則遞歸右子樹，k -= s，新區間根據進入右子樹的數量計算。
4. 直到 l==r 返回 sorted[l]。

代碼實現

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100010;
int val[20][MAXN], toLeft[20][MAXN], sorted[MAXN];

void build(int l, int r, int d) {
    if (l == r) return;
    int mid = (l+r)/2;
    int same = mid - l + 1;
    for (int i = l; i <= r; i++)
        if (val[d][i] < sorted[mid]) same--;
    int lpos = l, rpos = mid+1;
    for (int i = l; i <= r; i++) {
        if (val[d][i] < sorted[mid] || (val[d][i]==sorted[mid] && same>0)) {
            if (val[d][i]==sorted[mid]) same--;
            val[d+1][lpos++] = val[d][i];
            toLeft[d][i] = toLeft[d][i-1] + 1;
        } else {
            val[d+1][rpos++] = val[d][i];
            toLeft[d][i] = toLeft[d][i-1];
        }
    }
    build(l, mid, d+1);
    build(mid+1, r, d+1);
}

int query(int L, int R, int k, int l, int r, int d) {
    if (l == r) return val[d][l];
    int s = toLeft[d][R] - toLeft[d][L-1];
    if (k <= s) {
        int newL = l + toLeft[d][L-1];
        int newR = newL + s - 1;
        return query(newL, newR, k, l, (l+r)/2, d+1);
    } else {
        int newL = (l+r)/2 + 1 + (L-1 - l + 1 - toLeft[d][L-1]);
        int newR = newL + (R-L+1 - s) - 1;
        return query(newL, newR, k-s, (l+r)/2+1, r, d+1);
    }
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &val[0][i]);
            sorted[i] = val[0][i];
        }
        sort(sorted+1, sorted+n+1);
        build(1, n, 0);
        while (m--) {
            int i, j, k; scanf("%d%d%d", &i, &j, &k);
            printf("%d\n", query(i, j, k, 1, n, 0));
        }
    }
    return 0;
}

複雜度分析

構建 O(n log n)，單次查詢 O(log n)，總時間 O((n+m) log n)，空間 O(n log n)。