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

问题描述

给定一个整数数组和一些查询操作.
查询操作有两种类型
1.将第i个索引的值更新为x.
2.给定2个整数，找出该范围内的第k个最小值.(例如，如果2个整数是i和j，我们必须找出i和j之间的第k个最小值).
我可以使用段树找到范围最小查询，但对于第 k 个最小值则无法这样做.有人可以帮我吗?

解决方案

这里是一个 O(polylog n) 每个查询解决方案，它实际上不假设一个常量 k，因此 k 可以因查询而异.主要思想是使用段树，其中每个节点表示数组索引的间隔，并包含表示数组段中值的多重集(平衡二叉搜索树).更新操作非常简单:

1. 从叶子(您正在更新的数组索引)向上走段树.您将遇到表示包含更新索引的数组索引区间的所有节点.在每个节点，从多重集中删除旧值并将新值插入多重集中.复杂度:O(log^2 n)
2. 更新数组本身.

我们注意到每个数组元素都在O(log n)个多重集合中，所以总空间使用量为O(n log n).通过多集的线性时间合并，我们也可以在 O(n log n) 中构建初始段树(每个级别有 O(n) 工作).

查询呢?我们给定了一个范围 [i, j] 和一个秩 k 并且想要在 a[i..j]<中找到第 k 个最小的元素/代码>.我们该怎么做?

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.见下文.

那么选择算法是如何工作的呢?有一种非常简单的算法可以做到这一点.

我们有 s_1, ..., s_n 和 k 并且想要在 a 中找到最小的 xcode>，使得 s_1.rank(x) + ... + s_m.rank(x) >= k - 1，其中 rank 返回元素的数量小于各自 BBST 中的 x(如果我们存储子树大小，这可以在 O(log n) 中实现).我们就用二分查找找到x吧！我们遍历根的 BBST，进行几个排名查询并检查它们的总和是否大于或等于 k.它是 x 中的谓词单调，因此二进制搜索有效.答案是 x 在任何 s_i 中的最小后继者.

复杂度:每个查询O(n log n)预处理和O(log^3 n).

因此，对于 q 查询，我们总共得到了 O(n log n + q log^3 n) 的运行时间.我相信我们可以使用更聪明的选择算法将其简化为 O(q log^2 n).

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

• 预处理所有查询，创建一组数组中曾经出现过的所有值.数量最多为 q + n.
• 构建一个段树，但这次不是在数组上，而是在可能值的集合上.
• 线段树中的每个节点代表一个值区间，并维护这些值出现的一组位置.
• 要回答查询，请从段树的根开始.检查根的左子节点中有多少个位置位于查询间隔中(我们可以通过在位置的 BBST 中进行两次搜索来做到这一点).将该数字设为 m.如果 k <= m，则递归到左孩子.否则递归到右孩子，k 递减 m.
• 对于更新，从覆盖旧值的 O(log (q + n)) 节点中删除位置，并将其插入到覆盖新值的节点中.

这种方法的优点是我们不需要子树大小，因此我们可以使用平衡二叉搜索树的大多数标准库实现来实现它(例如，C++ 中的 set).

我们可以通过将段树更改为 权重平衡树，例如 BB[α] 树.与其他平衡二叉搜索树一样，它具有对数运算，但允许我们在子树变得不平衡时从头开始重建整个子树，将重建成本计入必然导致不平衡的操作.

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?

解决方案

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. Walk up the segment tree from the leaf (the array index you're updating). You will encounter all nodes that represent an interval of array indices that contain the updated index. At every node, remove the old value from the multiset and insert the new value into the multiset. Complexity: O(log^2 n)
2. Update the array itself.

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).

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. 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.

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.

Complexity: O(n log n) preprocessing and O(log^3 n) per query.

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.

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:

• 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.

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++).

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.

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