我這幾天稍微看了一下區間第 k 大，不知道自己想的對不對，
上來跟大家討論一下。 （不好意思這篇很長）
題目是這樣： 給定 n 個整數的陣列 A，以及 m 個查詢 [lj, rj], kj
找出 A[lj..rj] 的第 k 大數字
http://ppt.cc/24oD 這邊是 wiki 的介紹
以下是一些可行的方法，機器模型是 RAM 而且每個元素只使用 O(1) 空間，
假設 A[i] 的範圍是 [1..m]。
1. 類似 wiki 上面的方法（劃分樹）
建立一個樹的結構，每個節點代表著 [1..m] 的一個區間，
節點裡面紀錄一個陣列 B ，B[i] 代表 A[1..i]的元素中比 m / 2 小的個數。
樹根代表整個陣列，左子樹代表所有小於m/2的元素，右子樹代表剩下的元素，
可以遞迴建立起整棵樹。空間複雜度是O(n lg n)，查詢可以做到O(lg n)。
2. 幾何方法
給定一個查詢[lj, rj], kj時，我們可以用二分搜尋的方法來找出一個在[lj, rj]
中的元素，使得該元素在[lj, rj]中的 rank 為 kj。
對於任何元素 x ，如果我們可以在O(lg^2 n)的時間內計算
出 x 在 [lj, rj] 中的 rank，那只要binary search on x ，我們就可以得到
在O(lg^3 n)的時間內找出[lj, rj]中第 kj大的數字。
把輸入想像成平面上的 n 個點 (i, A[i])，找出 x 在 [lj, rj]中的 rank
其實等價於找出 lj <= i <= rj 且 A[i] >= x 的點個數。
就變成3-side range query了，用 range tree 或是 priority search tree，
都可以在O(lg^2 n)作 counting query。
priority search tree有點類似歸併樹。
如果可以使用fractional cascading或是generalized selection，
那區間 k 大的查詢可以在O(lg^2 n)的時間完成。
3. Fully persistent data structure
另外一種同樣基於二分搜尋的想法，當要搜尋 x 在[lj, rj]的rank時，
因為rank(lj, rj, x) = rank(1, rj, x) - rank(1, lj-1, x)，
所以如果有一種資料結構，可以在O(lg n)的時間內作rank(1, j, x)的查詢，
那我們就可以在O(lg^2 n)的時間內找出[lj, rj]中第 kj 大的數字。
如果是計算rank(1, n, x)，那麼我們可以只要建立一個二元搜尋樹就好了。
但是因為是要 query rank(1, j, x)，我們需要一個資料結構，可以回朔到
第 j 次插入之後的狀態，同時間還可以查詢。
而fully persistent data structure就滿足要求。
這邊有另外一個幾何解釋，我們可以把第 i 個元素看成是一條從(i, A[i])
開始，往右平行 x 軸的射線。
rank(1, j, x)實際上就是計算從(j, x)往上平行 y 軸的射線與多少平行
x 軸的射線相交。
就變成window query，用 segment tree 可以在O(lg n)計算出來。
4. 主席樹
其實就是設計一個特殊的資料結構來加速二分搜尋。
在方法 2 和 3 中，rank的計算方法是很一般性的，但是在這個問題上，
其實不需要那麼一般性的 rank 計算法，因為會查詢的 x 是基於二分搜尋的。
所以要設計一個特殊的資料結構來加速。
藉由 3 的幾何解釋，我們知道rank(1, j, x)是對於 x 遞增的。
所以對於每一個 j ，可以使用一個 Fenwick tree 來維護rank(1, j, .)。
我們又知道rank(1, j, .)和rank(1, j+1, .)差別不大，所以可以使用
persistent data structure來建構這 n 個樹（這邊我們不需要fully的性質）。
計算rank(lj, rj, x)時，實際上是同時top-down traverse
兩顆Fenwick tree: rank(1, lj, .) 和 rank(1, rj, .)
查詢的時間複雜度是O(lg n)。
區間 k 大 加上修改
方法 1 我是不知道能不能變成動態。
方法 2 是動態的 3-side range query，查詢應該是可以做到O(lg^2 n)。
方法 3 的話就要改使用 retroactive data structures，不但可以查詢
第 j 次插入後的結果，還可以修改第 j 次的操作，結果反應到所有 > j的結構。
應該也是可以O(lg^2 n)。
方法 4 我看了很多文章還是不懂怎麼變成動態。
但是我自己想了一個動態的方法，不知道對不對。
當計算rank(1, j, x)時，利用方法 2 的幾何解釋，實際上是在計算
滿足 1 <= i <= j 且 A[i] >= x 的點數。
所以我們只要設計一個動態的資料結構支援2-side range query，
同時又可以對於二分搜尋加速即可。
因為rank(1, j, x)是對於 j 遞增的，所以理論上
對於 每一個 x 都維護一個 binary search tree ， 儲存所有的 i 滿足
A[i] <= x。但是這樣修改的操作會太慢。
所以在外層要使用一個 靜態樹 的結構，類似方法 1。
每個節點表示 [1..m] 的一個區間，儲存一個 binary search tree，其中元素
是所有的 i 滿足 A[i] 在這個區間的。
然後左子樹表示所有小於m/2的區間，右子樹表示剩下的區間。
二分搜尋的每一個查詢都可以在O(lg n)內完成，所以查詢複雜度為O(lg^2 n)。
修改的話只是把 binary search tree 的元素加入和刪除，複雜度也可為O(lg^2 n)。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.149
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1423156670.A.4C6.html
※ 編輯: FRAXIS (129.170.195.149), 02/06/2015 05:22:15