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
寫了一次後便放入武器庫
