Brief description:
給定一組區間,每次詢問 [a, b] 區間內第 k 小的數。
.. .
Analysis:
… 區間 k 小數問題,這類問題引出的演算法很多,互相之間都有聯繫,同時問題本身也有諸多擴展和變形,必須做總結。
首先,坊間流傳比較多的做法是歸併樹和劃分樹。
以 A = { 1, 7, 2, 5, 8, 3, 4, 6 } 為例,下面給出圖示:
[1 2 3 4 5 6 7 8] [1 7 2 5 8 3 4 6] root [1 2 5 7][3 4 7 8] [1 2 3 4][7 5 8 6] [1 7][2 5][3 8][4 6] [1 2][3 4][5 6][7 8] [1][7][2][5][8][3][4][6] [1][2][3][4][5][6][7][8] leaf 歸併樹 劃分樹
像這樣把歸併排序 (Merge Sort) 中,
的中間過程記錄下來的話,就得到了歸併樹。。(對應的、將快速排序 (Quick Sort) 的中間過程記錄下來,就得到了劃分樹。。
對於歸併樹,容易回答 x 在當前區間中的排名,因而可以設計一個給予二分答案的演算法。
對於詢問 ([a, b], k),具體做法是現在樹上找到所有組成 [a, b] 的區間,之後得到 x 在所有這些區間中的排名並和 k 進行比較。
總的時間複雜度是 O(nlog^3n)。。。
而對於劃分樹,可以直接完成上述詢問不需要二分答案,方法是再劃分樹的基礎上建立一個輔助樹 (Auxiliary Tree)。
T[lv][i] 記錄從區間開始到第 i 個位置結束時,有多少數被劃分到了左邊。。
這樣具體是對於詢問 ([a, b], k),可以確定最終答案是在左子樹還是在右子樹內,
同時根據 Auxiliary Tree 中存儲的信息,進一步縮小區間 [a, b]。
時間複雜度只有 O(nlogn)。。。
(代碼 →這裡。
//}/* .................................................................................................................................. */ const int N = int(1e5)+9, M = 18; int A[N], T[M][N]; int n, m; #define rt 0,0,n-1 #define lvv (lv+1) #define ml (l+r>>1) #define mr (ml+1) #define lc lvv,l,ml #define rc lvv,mr,r #define t T[lv][i] void Build(int lv, int l, int r){ if (l == r) return; int ll = l, rr = mr; FOR_1(i, l, r){ if (t <= A[ml]) T[lvv][ll++] = t; else T[lvv][rr++] = t; t = ll-l; } Build(lc), Build(rc); } /* int Query(int lv, int l, int r, int a, int b, int k){ if (l == r) return A[a]; int ll = a == l ? 0 : T[lv][a-1], rr = T[lv][b]; return rr - ll >= k ? Query(lc,l+ll,l+rr-1,k) : Query(rc,mr+a-l-ll,mr+b-l-rr,k+ll-rr); }*/ inline int Query(int lv, int l, int r, int a, int b, int k){ while (l < r){ int ll = a == l ? 0 : T[lv][a-1], rr = T[lv][b]; if (rr - ll >= k) a=l+ll,b=l+rr-1,r=ml; else a=mr+a-l-ll,b=mr+b-l-rr,k-=rr-ll,l = mr; ++lv; } return A[a]; } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif RD(n, m); REP(i, n) T[0][i] = RDD(A[i]); sort(A,A+n); Build(rt);int a,b,k;DO(m){ RD(a,b,k);--a,--b; OT(Query(rt,a,b,k)); } }
[1 7 2 5 8 3 4 6] [1 1 2 2 2 3 4 4] root [1 2 3 4][7 5 8 6] [1 2 2 2][0 1 1 2] [1 2][3 4][5 6][7 8] [1 1][1 1][1 1][1 1] [1][2][3][4][5][6][7][8] —————————————————————— leaf 劃分樹 對應輔助樹
注意通常我們只需要 Auxiliary Tree,而不需要劃分樹,為了節約空間開銷,我們只需要保存其 Auxiliary Tree 就好。
另外注意到對於葉子節點,輔助樹是沒有定義的,上面的程序中在劃分樹的每個非葉子結點,
在完成了對應的建樹時刻的功能後,都被對應的 Auxiliary Tree 的結點覆蓋了。
(注意所有葉子結點是沒有被覆蓋的。。。在詢問的到葉子結點的時候,也可以返回 T[lv][l] 。。 )
歸併樹代碼移步 →這裡 。。。
(歸併樹思維複雜度雖然要低於劃分樹。。但是程序要難寫多了。。)
—————————— UPD:
下面介紹 xiaodai 學長教我的 O(nlog^2n) 演算法。。。對 A 數組的值域,建立線段樹。。(所以先要排序離散化。。。
線段樹的每個結點,保存一個有序數組,存儲 A 數組中,所有在這個值域的數的下標。。
這樣對於每個詢問 ([a, b], k),從線段樹的根節點開始,每次根據左子樹下標分布在 [a, b] 區間中數字的個數,
決定向左子樹遞歸還是向右子樹遞歸。。。。
(這一步要二分查找,劃分樹里這一步是通過在輔助數組上直接做差得到的。。
.. 完整代碼。。)
[1 2 3 4 5 6 7 8] [1 7 2 5 8 3 4 6] root [1 3 6 7][2 4 5 8] [1 2 3 4][7 5 8 6] [1 3][6 7][4 8][2 5] [1 2][3 4][5 6][7 8] [1][3][6][7][4][8][2][5] [1][2][3][4][5][6][7][8] leaf 值域線段樹 劃分樹
我們發現這種 「線段樹」 其實對應劃分樹的 Pos 版本。(取位置。。。
因而也可以向劃分樹中那樣,建立 Auxiliary Tree,得到 O(logn) 回答詢問的方法,其實完全是一個東西。
(值得注意的是左邊的 「線段樹」 建立起來的方式,實際上是反向,從葉子結點開始做歸併樹。。。
(可見歸併樹與劃分樹之間的種種聯繫。。同時也再次讓我們看到了劃分樹中,用輔助數組決定遞歸方向的同時縮小詢問區間的思想是多麼精髓啊!。。。
External link:
http://poj.org/problem?id=2104
http://www.notonlysuccess.com/index.php/divide-tree/