给定一个数字数组 a[0], a[1], ..., a[n-1]，我们得到这样的查询:
输出 k-a[i], a[i+1], ..., a[j] 范围内的第一个最大数
这些查询能否在每个查询的多对数时间(n)内得到回答？如果不是，是否有可能对结果进行平均并仍然获得良好的摊销复杂性？
编辑:这可以使用持久线段树来解决 http://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/
最佳答案
是的，如果 O(n log n) 空间可用，这些查询可以在 polylog 时间内得到回答。
通过构造深度为 log(n) 的线段树来预处理给定的数组。因此叶节点与源数组相同，下一个深度节点包含已排序的 2 元素子数组，下一级包含通过合并这些 2 元素数组生成的 4 元素数组等。换句话说，执行合并排序但是将每个合并步骤的结果保存在单独的数组中。这是一个例子:
root: | 1 2 3 5 5 7 8 9 |
| 1 2 5 8 | 3 5 7 9 |
| 1 5 | 2 8 | 7 9 | 3 5 |
source: | 5 | 1 | 2 | 8 | 7 | 9 | 5 | 3 |
要回答查询，请将给定范围拆分(最多分为 2*log(n) 个子范围)。例如，范围 [0, 4] 应拆分为 [0, 3] 和 [4]，这会给出两个排序数组 [1 2 5 8] 和 [7]。现在问题简化为在多个排序数组中查找第 k 个元素。解决它最简单的方法是嵌套二分查找:首先使用二分查找从每个数组中从最大的开始选择一些候选元素；然后在其他(较小的)数组中使用二进制搜索来确定该候选元素的排名。这允许在 O(log(n)^4) 时间内获取第 k 个元素。可能一些优化(如分数级联)或其他一些算法可以更快地做到这一点......
关于algorithm - 间隔顺序统计，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26296624/