查找数组中元素 >= k 的最大连续范围的次线性算法
Sublinear algorithm to find the maximum contiguous range with elements >= k in an array
给你一个长度为 N 的数组 A，其中包含自然数。
问题是：给定一个索引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²) 数据结构。
是的，这是可能的。您可以使用一种特殊的数据结构，这种数据结构可以在线性时间内构建并在 O(1) 内回答范围最大查询。它比较复杂，你可以阅读它here。当我们有了这个数据结构后，我们可以使用二分查找找到最大的可行m。每次查询需要 O(log N) 时间。
给你一个长度为 N 的数组 A，其中包含自然数。
问题是：给定一个索引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²) 数据结构。
是的，这是可能的。您可以使用一种特殊的数据结构，这种数据结构可以在线性时间内构建并在 O(1) 内回答范围最大查询。它比较复杂，你可以阅读它here。当我们有了这个数据结构后，我们可以使用二分查找找到最大的可行m。每次查询需要 O(log N) 时间。