PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 主席樹？

看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間9年前 (2015/02/06 01:17)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串3/4 (看更多)

我這幾天稍微看了一下區間第 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