计算静态数组中的最小查询背后的逻辑是什么？
What is the logic behind calculating minimum queries in static arrays?
我正在阅读有关静态数组查询的内容，这是我发现的内容：
最小查询：有一种 O(nlogn) 时间预处理方法，之后我们可以在 O(1) 时间内回答任何最小查询。
The idea is to precalculate all values of min(a, b) where b - a + 1 (the length of the range) is a power of two. The number of precalculated values is O(nlogn), because there are O(logn) range lengths that are powers of two.
可以使用递归公式有效地计算这些值：
分钟(a,b) = 分钟(分钟(a, a + w - 1), 分钟(a + w, b))
其中 b-a+1 是 2 的幂并且 w = (b - a + 1) / 2
上面引用的部分是什么意思？为什么我们只计算特定长度的最小值？
它背后的想法和直觉是什么？逻辑是做什么的？
有一种预感，它一定与二叉树有关，因为我们考虑的只是长度的 2 的幂。
此结构称为 RMQ，即范围最小查询。它通过利用 min 运算的结合性和交换性（即 min(x,y) = min(y,x) 和 min(x,y,z) = min(x,min(y,z) 来实现其 O(1) 查询). min的另一个属性是min(x,x) = x，更重要的是，min(x,y,z) = min(min(x,y),min(y,z))
如果每个长度为 2 的幂的每个子数组的所有 mins（因此 n log n 内存），您可以通过采用 min 的最大 2 次方，从 l 开始，不会超过 r，具有 2 的最大次方的最小值 结束于 r，不低于 l。这里的思路如下：
arr=[a,b,c,d,e,f,g,h]
我们计算 RMQ 的分钟数如下：
长度为 1：[min(a), min(b), min(c), etc]
长度 2：[min(a,b), min(b,c), min(c,d), min(d,e), etc]
长度为 4：[min(a,b,c,d}, min(b,c,d,e), min(c,d,e,f), etc]
要取从 1 到 6 的最小值，我们希望长度 4 的最小值范围从 1 开始（因为 8 会超过我们的正确索引），并取其中的最小值，长度 4 的最小值范围结束于6. 所以我们从数组 of length 4 中获取这些查询，并取最小值
min(of length 4[1], of length 4[2]) 这就是我们的答案。
我正在阅读有关静态数组查询的内容，这是我发现的内容：
最小查询：有一种 O(nlogn) 时间预处理方法，之后我们可以在 O(1) 时间内回答任何最小查询。
The idea is to precalculate all values of min(a, b) where b - a + 1 (the length of the range) is a power of two. The number of precalculated values is O(nlogn), because there are O(logn) range lengths that are powers of two.
可以使用递归公式有效地计算这些值：
分钟(a,b) = 分钟(分钟(a, a + w - 1), 分钟(a + w, b))
其中 b-a+1 是 2 的幂并且 w = (b - a + 1) / 2
上面引用的部分是什么意思？为什么我们只计算特定长度的最小值？
它背后的想法和直觉是什么？逻辑是做什么的？
有一种预感，它一定与二叉树有关，因为我们考虑的只是长度的 2 的幂。
此结构称为 RMQ，即范围最小查询。它通过利用 min 运算的结合性和交换性（即 min(x,y) = min(y,x) 和 min(x,y,z) = min(x,min(y,z) 来实现其 O(1) 查询). min的另一个属性是min(x,x) = x，更重要的是，min(x,y,z) = min(min(x,y),min(y,z))
如果每个长度为 2 的幂的每个子数组的所有 mins（因此 n log n 内存），您可以通过采用 min 的最大 2 次方，从 l 开始，不会超过 r，具有 2 的最大次方的最小值 结束于 r，不低于 l。这里的思路如下：
arr=[a,b,c,d,e,f,g,h]
我们计算 RMQ 的分钟数如下：
长度为 1：[min(a), min(b), min(c), etc]
长度 2：[min(a,b), min(b,c), min(c,d), min(d,e), etc]
长度为 4：[min(a,b,c,d}, min(b,c,d,e), min(c,d,e,f), etc]
要取从 1 到 6 的最小值，我们希望长度 4 的最小值范围从 1 开始（因为 8 会超过我们的正确索引），并取其中的最小值，长度 4 的最小值范围结束于6. 所以我们从数组 of length 4 中获取这些查询，并取最小值
min(of length 4[1], of length 4[2]) 这就是我们的答案。