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-)，男，河北人，硕士研究生，主要研究领域为系统软件支撑、并行计算。