给定一个由 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。这些元素中的第四个元素是 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
最佳答案
解决此任务的一种可能方法是使用不可变二叉 (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) 空间。
关于arrays - 数组查询，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32794362/