间隔的订单统计

间隔的订单统计

是的，如果

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]

，这给出了两个排序数组

[12 58]

和

[7]

。现在，该问题已简化为在多个排序的数组中找到第k个元素。解决它的最简单方法是嵌套二进制搜索：首先使用二进制搜索从每个数组中选择一个从最大数组开始的候选元素；然后在其他（较小）数组中使用二进制搜索来确定此候选元素的等级。这允许及时获得第k个元素

O(log(n)^4)

。也许某些优化（例如分数级联）或其他某种算法可以更快地完成此任务…