給定長度 n (≤100,000) 的互不相同整數數組，回答 m (≤5,000) 個查詢：區間 [i, j] 中第 k 小的數是多少？
示例：a = [1,5,2,6,3,7,4]，查詢 Q(2,5,3) → 區間 [5,2,6,3] 排序後 [2,3,5,6]，第 3 小為 5。
POJ 2761 區間不包含關係可用「排序值 + 平衡樹維護位置」。但本題區間任意重疊，存在包含關係，無法離線排序處理，需在線數據結構。
類似線段樹，但每層將區間按中位數劃分：左子樹存 ≤ 中位數的元素，**保持相對順序**；右子樹存 > 中位數的元素。構建過程記錄每個位置進入左子樹的元素個數 num[level][pos]。
// val[0][i] = 原始數組
// 排序副本 sorted[1..n] 用於確定中位數
void build(int l, int r, int level) {
if (l == r) return;
int mid = (l + r) >> 1;
int mid_val = sorted[mid];
int same = mid - l + 1; // 左子樹應分配個數
int lpos = l, rpos = mid + 1;
for (int i = l; i <= r; ++i) {
if (val[level][i] < mid_val) {
val[level+1][lpos++] = val[level][i];
num[level][i] = num[level][i-1] + 1;
} else if (val[level][i] > mid_val) {
val[level+1][rpos++] = val[level][i];
num[level][i] = num[level][i-1];
} else { // 等於中位數，優先填左子樹直到滿額
if (same > 0) {
val[level+1][lpos++] = val[level][i];
num[level][i] = num[level][i-1] + 1;
--same;
} else {
val[level+1][rpos++] = val[level][i];
num[level][i] = num[level][i-1];
}
}
}
build(l, mid, level+1);
build(mid+1, r, level+1);
}
查詢 [L, R] 第 k 小：
int query(int L, int R, int k, int l, int r, int level) {
if (l == r) return val[level][l];
int mid = (l + r) >> 1;
int in_left = num[level][R] - num[level][L-1]; // 區間內落入左子樹的個數
if (in_left >= k) {
// 答案在左子樹，新區間為左子樹中對應位置
int newL = l + num[level][L-1];
int newR = newL + in_left - 1;
return query(newL, newR, k, l, mid, level+1);
} else {
// 答案在右子樹，第 k-in_left 小
int newL = mid + 1 + (L - l - num[level][L-1]);
int newR = newL + (R - L + 1 - in_left) - 1;
return query(newL, newR, k - in_left, mid+1, r, level+1);
}
}
| 概念 | 說明 |
|---|---|
val[level][i] | 第 level 層第 i 位置的值 |
num[level][i] | 第 level 層前 i 個位置中，進入左子樹的個數（前綴和） |
| 中位數選擇 | 用排序後數組的中位數，保證左右子樹大小平衡 |
| 等於中位數處理 | 優先分配給左子樹，直到左子樹達到應有大小 |
| 查詢映射 | 通過 num 前綴和將原區間映射到子樹區間 |
劃分樹是主席樹的前身。主席樹每版本對應前綴，查詢直接用兩版本相減，代碼更簡潔、常數更小。但劃分樹無需動態分配節點，數組實現極快，仍是競賽常用選擇。
本題是「區間第 k 小」的經典在線問題。劃分樹通過「按值域劃分 + 記錄位置映射」將問題轉化為在子樹中遞歸查詢。掌握構建時的等值元素分配邏輯、查詢時的區間映射公式是核心。面試中可對比劃分樹、主席樹、線段樹套平衡樹、莫隊算法等多種解法優劣。
