algorithm - 查找数组中元素 >= k 的最大连续范围的次线性算法

Question

给你一个数组 A长度N包含自然数。 问题是:给个索引i和一个自然数 k ，最大偏移量是多少 m这样子数组中的所有元素 A[i,i+m]大于或等于 k .

有一个简单的 O(N) 算法:从 i 开始并向右扫描数组，直到找到 A[i+m] < k 的偏移量.

我正在寻找的是一种算法和数据结构，这样:

• 数据结构可以在最多 O(N log N) 的时间内从给定的数组中计算出来
• 数据结构的大小最多为 O(N)
• 该算法使用预先计算的数据结构最多在 O(log N) 中解决上述问题。

任何人都可以构建这样的算法吗？或者是否有一个很好的论据说明为什么这样的算法不存在？

我能想出的最好的事情涉及在 O(N²) 和 O(log N) 查找中构建的 O(N²) 数据结构。

Answer 1

是的，这是可能的。您可以使用一种特殊的数据结构，该结构可以在线性时间内构建并在 O(1) 中回答范围最大查询。它比较复杂，你可以阅读它here .当我们有这个数据结构时，我们可以使用二进制搜索来找到最大的可行m。每次查询需要 O(log N) 时间。