提问人：user8524786 提问时间：8/19/2022 最后编辑：Matt Timmermansuser8524786 更新时间：8/20/2022 访问量：592
恒定时间内任何子阵列的最大值和最小值
Maximum & Minimum of any subarray in constant time
问：
我是一名计算机科学工程专业的学生，我在许多任务中都遇到了这个问题。
我得到了一个带有值的大小
数组，然后询问了一些查询
。
在每个查询中，我都会得到两个索引，其中
.
我相信，如果进行了一些预处理，有一种方法可以回答这个问题。
我必须在.
这个问题我已经很多天了，但我根本无法理解。
答：
4赞
Matt Timmermans
8/19/2022
#1
此问题称为“范围最小查询”。它经过了充分的研究，如果你在谷歌上搜索一下，你最终会得到众所周知的、非常聪明的、相当复杂的数据结构，它满足了你的要求，需要 O（N） 空间和预处理时间。
在这里，我将提供一个更简单的解决方案，当您的数组包含少于 264 个项目时，该解决方案在实践中表现更好......即，总是。
我只谈谈找到最小值，但当然找到最大值需要类似的结构。
与众所周知的数据结构一样，它使用这个作为组件：
简单的 O（N log N） 空间解决方案
给定一个包含 N 个项目的数组 A，设 M = ceil（log2 N）。
制作一个大小为 NxM 的矩阵 W，对于每个 （i，j），其中 0 < i < N 和 1 < j < M，将 W[i][j] 分配给从 A[i] 开始的 2个 j 元素中最小值的索引，在数组的末尾停止。
所以现在，对于每个大小为 2j 的窗口，我们有其最小值的索引。由于每个子数组最多被 2 个重叠窗口覆盖，因此我们可以通过检查这 2 个窗口并选择其 2 个最小值中的较低值来轻松找到任何子数组中的最小值。
初始化此数据结构可以在每个项目的恒定时间内完成。如果先执行较小的窗口大小，则可以通过合并 2 个较小窗口的结果来找到每个窗口最小值。
此解决方案需要为每个数组项存储日志 N 索引。
O（N）空间解决方案
为了使解决方案适合 O（N） 空间，我们需要在 2 个级别使用上述数据结构：
- 将输入分成 64 个元素的块。选择每个块中最小的项目作为其代表。为代表数组实现 O（N log N） 解决方案。鉴于 N < 2 64，这要求每个块存储少于64 个索引，即每个项目最多存储一个索引 -- O（N）
- 为每个块中的 64 个项目分别实现 O（N log N） 解决方案。这需要每件商品最多存储 6 个索引，尺寸为 64、32、16、8、4、2。但是每个索引只需要 6 位或更少。窗口大小 2 的索引仅占用 1 位。因此，这 6 个索引可以打包到每个项目一个 32 位字中——再次 O（N）。（实现说明：仍然在阵列端切断窗口，而不是块端）
现在，我们每个项目只花费了 8 或 12 个字节（取决于数组索引是 32 位还是 64 位），我们可以轻松地在恒定时间内回答任何范围最小查询：
- 最多检查 2 个重叠的块表示窗口，以查找查询涵盖的所有完整块中的最小值;
- 最多检查 2 个部分块窗口以覆盖查询的其余部分;
- 返回找到的最小值。
上一个：将完整单词日期转换为数字
下一个：带权重的位掩码
评论
O(1)lrO(1)O(1)O(log(N))O(N)O(N)