arrays - 数组查询

Question

给定一个包含 N 个正整数的数组，A1,A2,...,An。您必须回答 Q 个问题。每个查询由两个整数 L 和 K 组成。对于每个查询，当所有这些元素按照其索引的递增顺序列出时，我必须告诉数组中大于或等于 L 的第 K 个元素。

示例 A = 22,44,12,16,14,88,25,49

查询 1:L = 3 K = 4由于所有元素都大于 3。所以我们列出整个数组，即 22、44、12、16、14、88、25、49。这些元素中的第4个元素是16

查询 2:L = 19 K = 5列出的元素 22、44、88、25、49。其中第 5 个元素是 49。

我所做的:对于每个查询，遍历整个数组并检查大于或等于 L 的第 K 个元素。复杂度:O(Q*N)

我需要的是:O(Q*logN) 复杂度。

约束:1<=Q<=10^5 1<=N<=10^5 1<=Ai<=10^5

Answer 1

解决此任务的一种可能方法是使用不可变二叉 (RB) 树。

首先，您需要按升序对数组进行排序，将元素的原始索引存储在元素旁边。

以倒序(降序)遍历数组，将元素一个一个添加到不可变二叉树中。树中的键是元素的原始索引。树是不可变的，所以通过添加元素我的意思是用添加的元素构建新树。将在每个步骤中创建的树保存在相应元素(最后添加到树中的元素)附近。

为每个元素构建这些树后，您可以在 O(log N) 时间内完成查询。

查询:首先，在排序数组 (O(log N)) 中对 L 进行二分查找，寻找大于 L 的元素。您会找到大于 L 的元素和对应的元素索引树。在这棵树中，您可以在 O(log N) 时间内找到 K 最大的索引。

整个算法将花费 O(N log N + Q log N) 时间。我不相信可以做得更好(因为对原始数组进行排序似乎是不可避免的)。

---

这种方法的关键是使用不可变的二叉树。此结构具有可变二叉树的属性，例如 O(log N) 中的插入和搜索，同时保持不可变。当您向此类树添加元素时，将保留该树的先前版本，仅重新创建与该树的先前“版本”不同的节点。通常是 O(log N) 个节点。因此，从数组元素创建 N 棵树将需要 O(N log N) 时间和 O(N log N) 空间。

您可以使用 immutable RB tree implementation in Scala作为引用。