范围内的Kth最小值 [英] Kth minimum in a Range

问题描述

给出一个整数数组和一些查询操作。

查询操作有2种类型

1.将ith索引的值更新为x。

2.给出2个整数找到该范围内的第k个最小值（例如，如果2个整数分别为i和j，则必须找出i和j之间的第k个最小值）。

我可以使用段树找到范围最小值查询，但对于第k个最小值却找不到。
有人可以帮我吗？

Given an array of integers and some query operations.
The query operations are of 2 types
1.Update the value of the ith index to x.
2.Given 2 integers find the kth minimum in that range.(Ex if the 2 integers are i and j ,we have to find out the kth minimum between i and j both inclusive).
I can find the Range minimum query using segment tree but could no do so for the kth minimum. Can anyone help me?

推荐答案

这是 O（polylog n）实际上不假设常数 k ，因此 k 可能在查询之间有所不同。主要思想是使用段树，其中每个节点代表一个数组索引的间隔，并包含重新表示的数组段中值的多集（平衡二进制搜索树）。更新操作非常简单：

Here is a O(polylog n) per query solution that does actually not assume a constant k, so the k can vary between queries. The main idea is to use a segment tree, where every node represents an interval of array indices and contains a multiset (balanced binary search tree) of the values in the represened array segment. The update operation is pretty straightforward:

1. 从叶子（您要更新的数组索引）中找出段树。您将遇到所有代表包含更新索引的数组索引间隔的节点。在每个节点上，从多重集中删除旧值，然后将新值插入多重集中。复杂度： O（log ^ 2 n）


2. 更新数组本身。

我们注意到每个数组元素都将位于 O（log n）多重集中，因此总空间使用量为 O（n log n）。利用多集的线性时间合并，我们还可以在 O（n log n）中构建初始分段树（还有 O（n）每个级别的工作）。

We notice that every array element will be in O(log n) multisets, so the total space usage is O(n log n). With linear-time merging of multisets we can build the initial segment tree in O(n log n) as well (there's O(n) work per level).

查询怎么样？我们得到了一个范围 [i，j] 和一个排名 k ，并且想找到第k个最小的元素在 a [i..j] 中。我们该怎么做？

What about queries? We are given a range [i, j] and a rank k and want to find the k-th smallest element in a[i..j]. How do we do that?

1. 使用标准细分树查询过程查找查询范围的不连续覆盖范围。我们得到 O（log n）不相交的节点，其多集的并集恰好是查询范围内值的多集。让我们将这些多集称为 s_1，...，s_m （其中 m< = ceil（log_2 n））。查找 s_i 花费 O（log n）时间。


2. 执行一个在联盟上进行 select（k） 查询的 s_1，...，s_m 。见下文。

1. Find a disjoint coverage of the query range using the standard segment tree query procedure. We get O(log n) disjoint nodes, the union of whose multisets is exactly the multiset of values in the query range. Let's call those multisets s_1, ..., s_m (with m <= ceil(log_2 n)). Finding the s_i takes O(log n) time.
2. Do a select(k) query on the union of s_1, ..., s_m. See below.

那么选择算法如何工作？

So how does the selection algorithm work? There is one really simple algorithm to do this.

我们有 s_1，...，s_n 和 k 给定，想在 a 中找到最小的 x ，例如 s_1.rank（x）+ ... + s_m.rank（x）> = k-1 ，其中 rank 返回相应BBST中小于 x 的元素数（可以在 O（log n）如果我们存储子树大小）。
让我们只使用二进制搜索来找到 x ！我们遍历根的BBST，进行几个等级查询，并检查它们的总和是否大于或等于 k 。它是 x 中的谓语单调，因此二进制搜索有效。那么答案就是 x 在任何 s_i 中的最小值。

We have s_1, ..., s_n and k given and want to find the smallest x in a, such that s_1.rank(x) + ... + s_m.rank(x) >= k - 1, where rank returns the number of elements smaller than x in the respective BBST (this can be implemented in O(log n) if we store subtree sizes). Let's just use binary search to find x! We walk through the BBST of the root, do a couple of rank queries and check whether their sum is larger than or equal to k. It's a predicate monotone in x, so binary search works. The answer is then the minimum of the successors of x in any of the s_i.

复杂度： O（n log n）预处理和 O（log ^ 3 n ）。

总的来说，我们得到的运行时间为 O（n log n + q log ^ 3 n）用于 q 个查询。我相信我们可以使用更聪明的选择算法将其降低到 O（q log ^ 2 n）。

So in total we get a runtime of O(n log n + q log^3 n) for q queries. I'm sure we could get it down to O(q log^2 n) with a cleverer selection algorithm.

更新：如果我们正在寻找一种可以同时处理所有查询的离线算法，则可以得到 O（（n + q）* log n * log（q + n））使用以下算法：

UPDATE: If we are looking for an offline algorithm that can process all queries at once, we can get O((n + q) * log n * log (q + n)) using the following algorithm:

• 预处理所有查询，创建一个包含所有值的集合发生在数组中。这些数量最多为 q + n 。


• 构建一个细分树，但这一次不在数组上，而是


• 段树中的每个节点都代表一个值的间隔，并维持这些值出现的位置。


• 要回答查询，请从细分树的根开始。检查查询间隔中根的左子级中有多少个位置（我们可以通过在位置的BBST中进行两次搜索来做到这一点）。将该数字设为 m 。如果 k< = m ，则递归到左孩子。否则递归到正确的孩子中，将 k 递减 m 。


• 要进行更新，请从覆盖旧值的 O（log（q + n））节点中删除头寸，然后将其插入覆盖新值的节点中。

• Preprocess all queries, create a set of all values that ever occured in the array. The number of those will be at most q + n.
• Build a segment tree, but this time not on the array, but on the set of possible values.
• Every node in the segment tree represents an interval of values and maintains a set of positions where these values occurs.
• To answer a query, start at the root of the segment tree. Check how many positions in the left child of the root lie in the query interval (we can do that by doing two searches in the BBST of positions). Let that number be m. If k <= m, recurse into the left child. Otherwise recurse into the right child, with k decremented by m.
• For updates, remove the position from the O(log (q + n)) nodes that cover the old value and insert it into the nodes that cover the new value.

这种方法的优点是我们不需要子树大小，因此我们可以使用平衡二进制搜索的大多数标准库实现来实现树（例如C ++中的 set< int> ）。

The advantage of this approach is that we don't need subtree sizes, so we can implement this with most standard library implementations of balanced binary search trees (e.g. set<int> in C++).

我们可以通过更改为重量平衡树（例如BB） [α]树。它具有像其他平衡二叉搜索树一样的对数运算，但是当不平衡时，我们可以通过对必须引起不平衡的运算收取重建费用来重新构建整个子树。

We can turn this into an online algorithm by changing the segment tree out for a weight-balanced tree such as a BB[α] tree. It has logarithmic operations like other balanced binary search trees, but allows us to rebuild an entire subtree from scratch when it becomes unbalanced by charging the rebuilding cost to the operations that must have caused the imbalance.

这篇关于范围内的Kth最小值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！