我這幾天稍微看了一下區間第 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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1423156670.A.4C6.html ※ 編輯: FRAXIS (129.170.195.149), 02/06/2015 05:22:15