Kth Minimum Element Range Query Algorithm
Ren Hui-bin, Li Zheng
(School of Electronics and Information Engineering, Tongji University, Shanghai 201804)
Abstract: Considering the following problem: given an unsorted array of n elements and a sequence of intervals in the array, compute the kth minimum element in each of the subarrays defined by the intervals. In decision support system, having knowledge on the kth minimum value is more informative than the maximum value. Using pre-computing, segment tree and augmented red-black tree,this paper describes algorithms that use O(nlogn) space and need O(log3n) time to query.
Key words: range query; segment tree; augmented red-black tree


從20世紀70年代末開始，許多研究人員開始研究范圍查詢問題。范圍查詢問題定義如下：設A = a1,a2,…,an是某種數據類型的一個排列，通過預處理排列A來回答范圍查詢。范圍查詢由兩個下標i，j（1 ≤ i ≤ j ≤ n）和一個計算函數F(ai,…,aj)組成。
當排列A是數字并且計算函數F是計算輸入的總和時，這個問題可以通過線性預處理時間和常數查詢時間來解決：創建一個數組B，使得數組B中的元素bi 為數列A的前i個元素的總和，特別規定b0 = 0，則ai +…+ aj = bj – bi-1。
當計算函數F為輸入的最小值（最大值）時，這就是典型的RMQ(Range Minimum-Maximum Query)問題。通過利用最小值和最大值的特殊性質，Bender和Farach-Colton提出了一個O(n)的數據結構[1] ，它能在O(1)時間復雜度回答RMQ問題。
J. Gray將函數F分為分布型，代數型和全局型[2]。分布型函數可以將數據劃分為若干部分，對每一部分分別進行聚集計算，然后對每一部分的聚集結果再進行一次聚集計算得出最終結果。標準的分布函數有：COUNT、SUM、MIN、MAX。代數型聚集函數可以表示為分布型聚集函數的代數函數，例如AVG是代數型函數，可以表示為SUM/COUNT。全局型函數不能通過聚集的方法進行計算。
本文考慮了一個新的范圍查詢問題，定義計算函數F(ai,…,aj)為輸入的第k小元素，則問題為查詢數列ai,…,aj 上的第k小元素(簡記為KRMQ)。RMQ問題可以看成是KRMQ問題的特殊情況。在決策支持系統中，了解第k小元素就可以得到該范圍內排名最靠前的k個元素的最小值，這比僅僅依靠最大值獲得的信息要關鍵得多。該問題可以分為兩種情況：(1) 靜態查詢，查詢過程中數列中的元素不進行更改。(2) 動態查詢，查詢過程中允許對數列中的元素進行更改。
采用KRMQA(i, j, k)表示查詢數組A中下標i到下標j形成的區間【i, j】的第k小元素的值，【i, j】包括下標為i和j元素。對于表1中的數組A，KRMQA(1, 4, 2) = 3，因為3是【1,4】中的第2小元素。

A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]
2
8 6 3 4 1 5 7
表1 數組A
1問題分析
顯然，無論對于靜態查詢還是動態查詢，線性時間選擇[3]都可以在O(n)時間內獲得某范圍內的第k小元素。因此使用線性時間選擇算法，每次的查詢時間復雜度都為O(n)。當n比較小時，該算法是可行的；但隨著n變大，查詢時間會線性增長，以至于不能快速響應查詢請求。
第k小元素范圍查詢屬于范圍查詢范疇，關注的是查詢時間，因此如果通過預處理能將查詢時間減少，則進行預處理是上上之策。
若將所有區間上的第k小元素都預處理后保存到一個三維數組M[][][]中，則每次查詢【i, j】上的第k小元素只需要取M[i][j][k]。預處理時可以先對區間【i, j】進行排序，然后依次填充M[i][j][1…j-i+1]。事實上，利用數組A[1…n]的排序數組可以在O(n)時間內得到A[1…n-1]和A[2…n]的排序數組。因此，只需要對原數組進行一次排序，所有子數組的排序數組可以在O(n)的時間復雜度內從其它子數組的排序數組得到。這樣預處理的時間復雜度和空間復雜度都為O(n3)，查詢時間復雜度為O(1)。因為預處理的代價太大，它并不實用。
本文提出的算法是：定義S為A的排序數組，二分枚舉 S中的元素e，直到e為比【i, j】中小于k個元素大的最大的元素，則KRMQA(i, j, k) = e。偽代碼如下：
Element KRMQ(int i, int j, int k){
low = i, high = j;
while(low < high){
mid = (high + low + 1) / 2;
計算【i, j】中比S[mid]小的元素數量num;
if(num >= k) high = mid – 1;
else low = mid;
}
return S[low];
}
證明：假定KRMQA(i, j, k)的結果為s，那么s必然存在于A中。顯然，對于A中任意一個大于s的元素x，【i, j】中小于x的元素個數不小于k；對于A中任意一個不大于s的元素x，【i, j】中小于x的元素個數小于k。所以s為A中比【i, j】中小于k個元素大的最大的元素。證畢。
這樣，第k小元素范圍查詢就轉化為計算【i, j】中比某元素小的元素數量問題，可以利用累計信息來解決。
本文第二部分介紹了兩種解決第k小元素范圍查詢問題的算法，通過使用線段樹和擴展紅黑樹等數據結構，利用二分查找和累計信息的思想，降低了預處理的空間和查詢所需要的時間，并分析了算法的時間和空間復雜度。
2數據結構與算法
2.1 線段樹簡介
線段樹是一種較為平衡的二叉樹，樹中的每個結點對應一條線段[a, b]。樹中結點是葉子結點當且僅當它代表的線段為元線段（長度為1的線段）。非葉子結點都有兩個子樹，左子樹樹根對應線段[a , (a + b ) / 2]，右子樹樹根對應線段[( a + b ) / 2 + 1 , b]。
線段樹具有以下兩個性質：
性質1 長度范圍為[1, L]的一棵線段樹的高度不超過logL + 1。
性質2 線段樹把區間上的任意一條長度為L的線段都分成不超過2logL條線段。
存儲一棵線段樹的空間復雜度一般為O(L)。對于插入線段、刪除線段、查找元素、查找區間最值等操作，時間復雜度一般都為O(log L)。
線段樹有兩種結構：動態結構和靜態結構。一般來說，動態結構較為靈活，但速度較慢；靜態結構節省內存，速度較快。
2.2 靜態查詢算法
預處理：對于數組A[1..n]，根據下標建立線段樹。sorted[0…logn][1…n]保存線段樹每一層中所有結點代表子數組的排序數組。初始化sorted數組可以通過歸并排序來實現，時間復雜度為O(nlogn)。表1中的數組A形成的線段樹和sorted數組如圖1和表2所示。
查詢：sorted[0]為A的排序數組，根據問題分析的算法，只需要二分枚舉該數組中的元素v，計算【i, j】中小于v的元素數量。sorted數組中存在線段樹每條子線段所代表子數組【x, y】的排序數組，可以通過二分來查找子數組【x, y】中比s小的元素數量。根據線段樹的性質2，【i, j】最多分成2log(n)條子線段，如【2,7】可以分成4條子線段：【2,2】，【3,4】，【5,6】，【7,7】。因此計算【i, j】內小于s的元素數量時間復雜度為O(log2n)，查詢的時間復雜度為O(log3n)。
更改元素：如果要更改A[i]，則線段樹中每個包括A[i]的結點代表的子數組的排序數組都需要計算，總時間為





所以時間復雜度為O(n)。圖1中的黑色結點為修改A[3]需要更新的所有子數組。

圖1 數組A形成的線段樹

數組S S[1] S[2] S[3] S[4] S[5] S[6] S[7] S[8]
sorted[0]
1 2 3 4 5 6 7 8
sorted[1] 2 3 6 8 1 4 5 7
sorted[2] 2 8 3 6 1 4 5 7
sorted[3] 2 8 6 3 4 1 5 7
表2 預處理后的sorted數組
2.3 擴展紅黑樹
擴展紅黑樹是在紅黑樹[4]的每個結點增加一個size域和一個weight域的二分查找樹。weight表示與該元素相同的元素數量，相同的元素只需要一個結點來表示。size表示以該結點為根的子樹中所有結點的weight的總和，即樹中元素數量的總和。
struct RBNode{
Element key; //元素值，或稱主鍵
int weight; //相同元素數目
int size; //以該結點為根的子樹中元素總數
bool color; //結點為紅色還是黑色
RBNode* left, *right, *parent;
};
建樹的時間復雜度與普通紅黑樹相同，為O(nlogn)。
插入操作分兩步進行。如插入元素v，首先查找樹中是否有結點的主鍵等于v，同時將所經過路徑上的所有結點的size值增加1，因為這些結點形成的子樹增加了一個元素。如果存在這樣的結點，那么不需要插入新結點，只將該結點的weight值增加1；否則插入一個新結點p，p.key = v，p.weight = p.size = 1，并調整紅黑樹。時間復雜度為O(logn)。
假定總是先插入后刪除，則樹中總存在主鍵為v的結點。如果刪除元素v，查找等于該元素的結點，將該結點的weight減少1，同時將所經過路徑上的所有結點的size減少1。如果該結點weight為0，說明沒有元素使用該結點，刪除該結點，并調整紅黑樹；否則說明有其他元素共享該結點，操作結束。時間復雜度為O(logn)。
由size值和weight值的定義可知，根據size和weight可以在O(logn)時間內獲得任意結點在樹中的排名。因此計算樹中比某元素v小的元素數量可以通過查找樹中不小于v的最小元素所在結點X來計算：如果樹中不存在不小于v的元素，則直接返回根結點size值，否則返回X結點在樹中的排名減1。
2.4 動態查詢算法
預處理：在線段樹的每個結點建立一棵擴展紅黑樹，保存該子數組的所有元素。對于線段樹的每一層，任意元素必然存在于該層的某一棵擴展紅黑樹中。最壞情況下，元素各不相同，則每個元素在線段樹每一層的樹中都需要一個結點，線段樹共有logn+1層，所以空間復雜度為O(nlogn)。
一個n個結點的擴展紅黑樹建樹的時間復雜度為O(nlogn)，假設線段樹的某一層共有m個結點，結點中分別有ki個元素，則建立該層擴展紅黑樹的總時間為




線段樹共有(logn+1)層，所以預處理的時間復雜度為O(nlog2n)。
查詢：擴展紅黑樹是一棵二分查找樹，而線段樹第一層結點的擴展紅黑樹中包含了原數組的所有元素，所以KRMQA(i, j, k)可以通過二分枚舉該擴展紅黑樹中結點的主鍵key，計算【i, j】包含的所有子線段擴展紅黑樹中比key小的元素數量的總和來獲得。由3.3可知，計算擴展紅黑樹中比某元素小的元素數量的時間復雜度為O(logn)。由線段樹的性質2可知，【i, j】最多分成不超過2logn個子區間，因此最多在2logn棵擴展紅黑樹中進行計算比特定元素x小的元素數量的操作。所以計算【i, j】中比某元素小的元素數量的時間復雜度為O(log2n)。又二分枚舉擴展紅黑樹中的主鍵的時間復雜度為O(logn)，因此查詢的時間復雜度為O(log3n)。
更改元素操作需要對線段樹每一層包含該元素的結點的擴展紅黑樹中刪除該元素并插入該元素的新值。因為刪除元素的時間復雜度為O(logn)，最多有（logn+1）棵紅黑樹包含該元素，所以刪除操作的時間復雜度為O(log2n)。同理插入新元素的時間復雜度為O(log2n)。因此更改元素的時間復雜度為O(log2n)。圖1中的黑色結點為更改A[3]要更新的所有擴展紅黑樹。
3實驗與性能分析
根據第三部分的分析，本文算法所使用的額外空間復雜度、預處理的時間復雜度、查詢操作的時間復雜度和更改元素的時間復雜度如表3所示。

算法 額外空間 預處理時間 查詢時間 更改元素
靜態算法
O(n log n) O(n log n) O(log3 n) O(n)
動態算法 O(n log n) O(n log2 n) O(log3 n) O(log2 n)
表3 算法復雜度表
我們在一臺CPU1.6GHz，內存1GB的PC上進行實驗，數組A為隨機生成的整型數組，所有的查詢和更新操作也是隨機生成的，實驗結果如圖2，圖3，圖4所示。

圖2 預處理時間曲線圖 圖3 查詢時間曲線圖


圖4 更新時間曲線圖

從圖2來看，靜態算法的預處理更優秀。當數組大小為10萬時靜態算法只需要79ms，而動態算法需要4264ms。從圖3來看，雖然兩個算法的查詢時間復雜度相同，但靜態算法的效率更高。動態算法與靜態算法的運行時間的比值約為4。從圖4來看，動態算法的更改元素花費的時間要遠遠少于靜態算法。
因此，不需要更改元素時，靜態查詢算法不僅占用額外空間少，預處理時間少，查詢花費的時間小，實現的難度也不高，是不錯的選擇；需要經常更新元素時，數據量極小時靜態算法仍可以滿足需要，數據量大時則只能采用動態算法。
4總結
KRMQ問題是RMQ問題的一般化，它所提供的信息也比RMQ要關鍵得多。本文通過采用預處理技術，利用線段樹和擴展紅黑樹等數據結構給出了解決KRMQ問題的算法，分析了算法的性能，并做了相關實驗。據筆者所了解，迄今未見有文獻報導，也不確定解決KRMQ問題算法的下界，而且我們所采用的數據結構也不一定是最優的。因此對于KRMQ的研究，將來還有很多有意義的工作需要去做，特別是確定解決KRMQ問題的算法的下界。

參考文獻
[1] Bender, M. A., Farach-Colton. The LCA Problem Revisited[J]. //Gaston, G. H., Panario, D., Viola A., Proceedings of the 4th Latin American Symposium on Theoretical Informatics, London, Springer-Verlag, 2000: 88-94.
[2] Gray J., Bosworth A., Layman A., et al. Data Cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals[J]. //Stanley Y W. Su, Proceedings of the 12th International Conference on Data Engineering, Washington DC, IEEE Computer Society, 1996: 152 – 159.
[3] 盧開澄. 計算機算法導引—設計與分析[M]. 清華大學出版社, 1996: 136-138.
[4] Tomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction To Algorithm[M]. 2nd ed. [S.l.]:Higher Eduction Press/The MIT Press. 2002: 273 – 301.

作者簡介：
任會斌(1985-)，男，河北人，碩士研究生，主要研究領域為系統軟件支撐、并行計算。