HDU 2665 Kth Number：劃分樹（主席樹前身）模板詳解

問題

靜態數組，多次查詢區間第 k 小。n, m ≤ 10⁵，數值範圍大，需離線結構。

劃分樹核心思想

類似快速排序分治：每層將區間數值按中位數分為左右兩組，保持相對順序，記錄每個位置分到左邊的個數（toleft[dep][i]）。查詢時根據左側個數決定遞歸左或右子區間。

構建過程 build(l, r, dep)

1. 若 l==r 返回。
2. mid = (l+r)/2，sorted[mid] 為當前區間中位數。
3. 計算 same = 左半區間長度 - 已分入左側的「小於中位數」個數，用於處理等於中位數的元素分配。
4. 掃描 l..r，按 tree[dep][i] < sorted[mid] 或 == 且 same>0 分入左邊（tree[dep+1][lpos++]），否則右邊。同時構建 toleft[dep][i] = toleft[dep][l-1] + (lpos - l)。
5. 遞歸構建左右子區間。

查詢過程 query(L, R, l, r, dep, k)

• 若 l==r 返回 tree[dep][l]。
• cnt = toleft[dep][r] - toleft[dep][l-1] 為查詢區間落入左側的個數。
• 若 cnt ≥ k：遞歸左子區間，新邊界 newl = L + toleft[dep][l-1] - toleft[dep][L-1]，newr = newl + cnt - 1。
• 否則：遞歸右子區間，k -= cnt，新邊界類似計算。

複雜度

構建 O(n log n)，查詢 O(log n)，空間 O(n log n)。適合靜態區間第 k 小，代碼常數較小。