您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

HDU 2665 Kth Number 題解：劃分樹實現區間第 K 大查詢

編輯：C++ 入門

問題描述

給定長度 n (≤100,000) 的數列，回答 m (≤100,000) 個查詢：區間 [s, t] 中第 k 大的數是多少。多測試用例。

為什麼選擇劃分樹？

歸並樹（合併排序樹）查詢 O(log²n)，常數大，易超時。
劃分樹（Partition Tree）基於快速排序 partition 思想，構建 O(n log n)，查詢 **O(log n)**，適合大數據量。
線段樹 + 持久化（主席樹）也是 O(log n) 但代碼更複雜。

劃分樹核心原理

**構建階段**：將原數組複製並排序得到 `sorted[]`。遞歸構建：當前區間 [L,R] 的中位數 `mid = (L+R)/2`，以 `sorted[mid]` 為基準值 `key`。遍歷當前層數組 `seg[dep][i]`，將 `< key` 的放左邊，`> key` 的放右邊，`== key` 的優先填左邊直到左邊配額 `scnt = mid-L+1` 滿。同時維護 `lftnum[dep][i]` = 前 i 個元素中分到左邊的個數。遞歸處理左右子區間。
**查詢階段**：在區間 [s,t] 中找第 k 大。當前節點區間 [L,R]，左邊元素個數 `cnt = lftnum[dep][R] - lftnum[dep][s-1]`。若 `cnt >= k`，目標在左子樹，映射新區間 `[L + act, L + act + cnt - 1]` 遞歸；否則在右子樹，映射 `[mid + a + 1, mid + a + b]` 遞歸查找第 `k-cnt` 大。

關鍵數據結構

`seg[dep][i]`：第 `dep` 層第 `i` 位置的值。
`lftnum[dep][i]`：第 `dep` 層前 `i` 個元素中分入左子樹的計數（前綴和）。
`tree[rt]`：線段樹節點，存儲區間範圍 [lson, rson]。
`num[i]`：排序後的原數組（1-based）。

AC 代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 10;

struct Node { int lson, rson; int mid() { return (lson + rson) >> 1; } } tree[MAXN * 4];
int seg[25][MAXN];
int lftnum[25][MAXN];
int num[MAXN];
int n, m, sta, ed;

void build(int L, int R, int rt, int dep) {
    tree[rt].lson = L; tree[rt].rson = R;
    if (L == R) return;
    int mid = tree[rt].mid();
    int key = num[mid];
    int scnt = mid - L + 1; // 左邊應分配的個數（含等於 key 的一部分）
    for (int i = L; i <= R; ++i)
        if (seg[dep][i] < key) --scnt;

    int lp = L, rp = mid + 1;
    for (int i = L; i <= R; ++i) {
        lftnum[dep][i] = (i == L) ? 0 : lftnum[dep][i-1];
        if (seg[dep][i] < key) {
            ++lftnum[dep][i];
            seg[dep+1][lp++] = seg[dep][i];
        } else if (seg[dep][i] > key) {
            seg[dep+1][rp++] = seg[dep][i];
        } else {
            if (scnt > 0) { --scnt; ++lftnum[dep][i]; seg[dep+1][lp++] = seg[dep][i]; }
            else { seg[dep+1][rp++] = seg[dep][i]; }
        }
    }
    build(L, mid, rt<<1, dep+1);
    build(mid+1, R, rt<<1|1, dep+1);
}

int query(int L, int R, int rt, int dep, int k) {
    if (tree[rt].lson == tree[rt].rson) return seg[dep][L];
    int cnt, act;
    if (L == tree[rt].lson) { cnt = lftnum[dep][R]; act = 0; }
    else { cnt = lftnum[dep][R] - lftnum[dep][L-1]; act = lftnum[dep][L-1]; }
    int mid = tree[rt].mid();
    if (cnt >= k) {
        L = tree[rt].lson + act;
        R = tree[rt].lson + act + cnt - 1;
        return query(L, R, rt<<1, dep+1, k);
    } else {
        int a = L - tree[rt].lson - act;
        int b = R - L - cnt + 1;
        L = mid + a + 1;
        R = mid + a + b;
        return query(L, R, rt<<1|1, dep+1, k - cnt);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) {
            cin >> num[i];
            seg[0][i] = num[i];
        }
        sort(num+1, num+n+1);
        build(1, n, 1, 0);
        while (m--) {
            int k; cin >> sta >> ed >> k;
            cout << query(sta, ed, 1, 0, k) << '\n';
        }
    }
    return 0;
}