这里有一个O(polylog n)每个查询解决方案实际上并不假设一个常量k， 所以k查询之间可能有所不同。主要思想是使用线段树，其中每个节点代表数组索引的一个区间，并包含所代表的数组线段中的值的多重集（平衡二叉搜索树）。更新操作非常简单：
- 从叶子（您正在更新的数组索引）开始沿着线段树向上走。您将遇到表示包含更新索引的数组索引区间的所有节点。在每个节点，从多重集中删除旧值并将新值插入多重集中。复杂：
O(log^2 n)
- 更新数组本身。
我们注意到每个数组元素都会在O(log n)多重集，因此总空间使用量为O(n log n)。通过多重集的线性时间合并，我们可以构建初始线段树O(n log n)还有（有O(n)每个级别的工作）。
那么查询呢？我们给定一个范围[i, j]和一个等级k并想找到第 k 个最小的元素a[i..j]。我们该怎么做呢？
- 使用标准线段树查询过程查找查询范围的不相交覆盖范围。我们得到
O(log n)不相交的节点，其多重集的并集恰好是查询范围内的值的多重集。我们称这些多重集为s_1, ..., s_m (with m <= ceil(log_2 n)）。寻找s_i takes O(log n) time.
- Do a select(k) http://en.wikipedia.org/wiki/Selection_algorithm查询并集
s_1, ..., s_m。见下文。
那么选择算法是如何工作的呢？有一种非常简单的算法可以做到这一点。
We have s_1, ..., s_n and k给定并想要找到最小的x in a，使得s_1.rank(x) + ... + s_m.rank(x) >= k - 1, where rank返回小于的元素数量x在相应的 BBST 中（这可以在O(log n)如果我们存储子树大小）。
我们就用二分查找来查找x！我们遍历根的 BBST，进行几次排名查询并检查它们的总和是否大于或等于k。这是一个谓词单调x，所以二分查找有效。那么答案是最小的后继者x在任何一个s_i.
复杂: O(n log n)预处理和O(log^3 n)每个查询。
所以我们总共得到的运行时间为O(n log n + q log^3 n) for q查询。我相信我们可以把它归结为O(q log^2 n)具有更聪明的选择算法。
UPDATE:如果我们正在寻找一种可以一次处理所有查询的离线算法，我们可以得到O((n + q) * log n * log (q + n))使用以下算法：
- 预处理所有查询，创建数组中曾经出现过的所有值的集合。其数量最多为
q + n.
- 构建一个线段树，但这次不是在数组上，而是在可能值的集合上。
- 线段树中的每个节点代表一个值区间，并维护一组这些值出现的位置。
- 要回答查询，请从线段树的根开始。检查根的左子节点中有多少位置位于查询区间内（我们可以通过在位置的 BBST 中进行两次搜索来做到这一点）。令该数字为
m. If k <= m，递归到左孩子。否则递归到右孩子，k减少了m.
- 如需更新，请从
O(log (q + n))覆盖旧值的节点并将其插入到覆盖新值的节点中。
这种方法的优点是我们不需要子树大小，因此我们可以使用平衡二叉搜索树的大多数标准库实现来实现它（例如set<int>在 C++ 中）。
我们可以通过将线段树更改为权重平衡树，例如 BB[α] 树 http://www.eli.sdsu.edu/courses/fall95/cs660/notes/BB/BBtrees.html。它与其他平衡二叉搜索树一样具有对数运算，但允许我们在子树变得不平衡时从头开始重建整个子树，方法是将重建成本计入导致不平衡的操作。
