劃分樹

Definition

給出一條array A[], 對A[]建立劃分樹可以在 O(log N) 時間內解決
1. query(x,y,k) : 在 A[x..y]中的第k小元素
2. rank(x,y,k) : A[k] 在 A[x..y] 內排第幾

Structure

劃分樹和 segment tree 相似, root 代表 [1,n], 兩個 child 為 [1, n/2], [n/2+1, n]
每一個 node 是一條 array

Root是原本的A[]
然後, 把較少的一半分到 left subtree, 較大的一半分到 right subtree, 而各自的相對次序不變

例如

Root = [3 1 5 4 6 8 2 7]
Left child = [3 1 4 2]
Right child = [5 6 8 7]

同時要記著哪些元素分到了左子樹
以上面為例

[3  2  8  4  6  5  1  7]
[3  2  4  1][8  6  5  7]
[2  1][3  4][6  5][8  7]
[1][2][3][4][5][6][7][8]

Query

對於 query(x,y,k)
可視為 "在 [1,n] 入面 [x,y] 中的第k元素"
然後就要發揮二元樹的精神: 把問題 reduce 做一半

先判斷我們要的答案在 left subtree 還是在 right subtree
就可以把問題 reduce 成
"在 [1, n/2] 入面 [x', y'] 中的第 k' 元素" 或
"在 [n/2, 1] 入面 [x'', y''] 中的第 k' 元素"

那些 x',y',k' 怎樣計出來
方法不外乎利用記了哪些元素分到左子樹

至於 rank(x,y,k), 則原理相近

Implement

為方便起, 先把 A[] 離散化
就可以快速判斷分去 left subtree 還是 right subtree

然後棵 tree 其實是 log N 條 array
因為每一層都要記 N 個element的資料

記錄哪些元素分到了左子樹實際上是記 "在這個 node 中, 每個 element 左邊有多少個分到左子樹"
可用 partial sum 解決之
因為計那些 x', y', k' 等等都要用到 partial sum

其實 code 不長
不過細節很煩, 計 index 的式有 4-5 個 variable
寫了一次後便放入武器庫