间隔的订单统计 [英] Order statistic on intervals

问题描述

给出一个数字数组 a [0]，a [1]，...，a [n-1] ，我们得到以下类型的查询： / p>

输出 k 在 a [i]，a [i +1]，...，a [j]

这些查询能否在对数时间内得到回答（在中n ）？如果不是，是否有可能取平均结果并仍然获得良好的摊销复杂性？

EDIT ：这可以使用持久性段树$来解决。 b $ b http://blog.anudeep2011.com/persistent -segment-trees-exploned-with-spoj问题/

解决方案

可以，这些查询可以通过以下方式回答如果 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 | 
来源：| 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个元素。也许某些优化（例如分数级联）或其他一些算法可以更快地完成此操作...

Given an array of numbers a[0], a[1], ..., a[n-1], we get queries of the kind:

output k-th largest number in the range a[i], a[i+1], ..., a[j]

Can these queries be answered in polylogarithmic time (in n) per query? If not, is it possible to average results and still get a good amortized complexity?

EDIT: this can be solved using persistent segment trees http://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/

解决方案

Yes, these queries can be answered in polylog time if O(n log n) space is available.

Preprocess given array by constructing segment tree with depth log(n). So that leaf nodes are identical to source array, next-depth nodes contain sorted 2-element sub-arrays, next level consists of 4-element arrays produced by merging those 2-element arrays, etc. In other words, perform merge sort but keep results of each merge step in separate array. Here is an example:

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 |

To answer a query, split given range (into at most 2*log(n) subranges). For example, range [0, 4] should be split into [0, 3] and [4], which gives two sorted arrays [1 2 5 8] and [7]. Now the problem is simplified to finding k-th element in several sorted arrays. The easiest way to solve it is nested binary search: first use binary search to choose some candidate element from every array starting from largest one; then use binary search in other (smaller) arrays to determine rank of this candidate element. This allows to get k-th element in O(log(n)^4) time. Probably some optimization (like fractional cascading) or some other algorithm could do this faster...

这篇关于间隔的订单统计的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！