algorithm - 高效查找未排序列表前缀的顺序统计？

Question

A 是从 1 到 n 的随机整数数组。

我需要至少在记录时间内随机访问第一个 j 元素中的第 i 个最大元素。

到目前为止我得到的是一个n x n矩阵M，其中元素在(i, j)位置是第一个 j 中的第 i 个最大的。这为我提供了恒定时间的随机访问，但需要 n^2 存储空间。

根据构造，M 按行和列排序。此外，每一列都与其相邻列有一个值不同。

任何人都可以建议一种方法将 M 压缩到 n log(n) 空间或更好，使用 log(n) 或更好随机访问时间？

Answer 1

我相信您可以在 O(log(N)) 时间内执行访问，给定 O(N log(N)) 预处理时间和 O(N log(N)) 额外空间。方法如下。

您可以扩充红黑树以支持 select(i) 操作，该操作在 O(log(N)) 时间内检索排名 i 的元素。例如，see this PDF或算法导论的相应章节。

您可以以函数式方式实现一棵红黑树(即使是经过扩充以支持 select(i))，这样插入操作会返回一棵新树，除了 O(log) (N)) 节点与旧树。参见示例 Purely Functional Data Structures作者:克里斯冈崎。

我们将构建一个由纯功能增强红黑树组成的数组 T，这样树 T[j] 存储索引 0 ... A 的第 j-1 个 j 元素从大到小排序。

基本情况:在T[0]创建一棵只有一个节点的增广红黑树，其数据为数字0，即第1个中第0大元素的索引数组 A 的元素。

归纳步骤:对于从 1 到 N-1 的每个 j，在 T[j] 处创建一个增强的红黑树，通过纯粹从功能上将索引为 j 的新节点插入到树 T[j-1] 中。这最多创建 O(log(j)) 个新节点；其余节点与 T[j-1] 共享。这需要 O(log(j)) 时间。

构造数组 T 的总时间是 O(N log(N))，使用的总空间也是 O(N log(N))。

一旦创建了T[j-1]，就可以访问的前j个元素中的第i个最大元素>A 通过执行 T[j-1].select(i)。这需要 O(log(j)) 时间。请注意，您可以在第一次需要时延迟创建 T[j-1]。如果 A 非常大而 j 总是相对较小，这将节省大量时间和空间。