用于在优于 O(log n) 预期时间内找到子数组最大值的数据结构
Data structure for finding maximum of subarrays in better than O(log n) expected time
给定一个值数组，您如何构建一个数据结构来让您快速找到任何连续子数组的最大值？理想情况下，构建此结构的开销应该很小，并且该结构应该允许有效地附加和更改单个元素。
示例数组为 [6, 2, 3, 7, 4, 5, 1, 0, 3]。请求可能是找到从索引 2 到 7（子数组 [3, 7, 5, 1, 0]）的切片的最大值，这将导致 7.
设 n 为数组的长度，k 为切片的长度。
天真，O(log k)，方法
一个明显的解决方案是构建一棵重复给出最大值的成对摘要的树
1 8 4 5 4 0 1 5 6 9 1 7 0 4 0 9 0 7 0 4 5 7 4 3 4 6 3 8 2 4 · ·
8 5 4 5 9 7 4 9 7 4 7 4 6 8 4 ·
8 5 9 9 7 7 8 4
8 9 7 8
9 8
9
这些摘要最多占用O(n) space，并且可以通过使用短索引来有效地存储较低级别。例如，底层可以是位数组。附加和单个突变需要 O(log n) 时间。如果需要，还有许多其他方面需要优化。
所选切片可以拆分为两个切片，拆分在两个三角形之间的边界上。在此示例中，对于给定的切片，我们将这样拆分：
|---------------------------------|
6 9 1 7 0 4 0 9|0 7 0 4 5 7 4 3 4 6 3 8 2 4 · ·
9 7 4 9 | 7 4 7 4 6 8 4 ·
9 9 | 7 7 8 4
9 | 7 8
| 8
在每个三角形中，我们对这些树中的 forest 感兴趣，这些树最低限度地确定了我们实际关心的元素：
|---------------------------------|
1 7 0 4 0 9|0 7 0 4 5 7 4 3 4 6 3
7 4 9 | 7 4 7 4 6
9 | 7 7
| 7
请注意，在这种情况下，左边有两棵树，右边有三棵。树的总数最多为 O(log k)，因为任何给定高度最多有两棵。我们可以用一点bit-math
找到分裂点
round_to = (start ^ end).bit_length() - 1
split_point = (end >> height) << height
请注意，Python 的 bit_length 可以在 x86 架构上使用 lzcnt 指令快速完成。相关树位于拆分的每一侧。相关子树的大小编码在这些数字的残差位中：
lhs_residuals = split_point - start
rhs_residuals = end - split_point
bin(lhs_residuals)
# eg. 10010110
# sizes = 10000000
# 10000
# 100
# 10
很难遍历整数的最高有效位，但如果你进行位交换（一个字节交换指令加上一些 shift-and-masks），你就可以通过迭代这个来遍历最低有效位：
new_value = value & (value - 1)
lowest_set_bit = value ^ new_value
value = new_value
遍历左半边和右半边需要 O(log k) 预期时间，因为最多有 2log₂ k 棵树 - 每边一个位。
切线：在 O(1) 时间和 O(n log n) space
中处理残差
O(log k)优于O(log n)，但仍未开创先河。先前尝试的一个有益效果是每一侧的树都是 "attached" 一侧；他们的切片中只有 n 个范围，而任意切片中没有 n² 个范围。您可以通过添加到每个级别的累积最大值来利用它，如下所示：
1 8 4 5 4 0 1 5 6 9 1 7 0 4 0 9 0 7 0 4 5 7 4 3 4 6 3 8 2 4 · ·
- 8|- 5|- 4|- 5|- 9|- 7|- 4|- 9|- 7|- 4|- 7|- 4|- 6|- 8|- 4|- · left to right
8 -|5 -|4 -|5 -|9 -|7 -|4 -|9 -|7 -|4 -|7 -|4 -|6 -|8 -|4 -|· - right to left
- - 8 8|- - 4 5|- - 9 9|- - 4 9|- - 7 7|- - 7 7|- - 6 8|- - · · left to right
8 8 - -|5 5 - -|9 9 - -|9 9 - -|7 7 - -|7 7 - -|8 8 - -|4 4 - - right to left
- - - - 8 8 8 8|- - - - 9 9 9 9|- - - - 7 7 7 7|- - - - 8 8 · · left to right
8 8 5 5 - - - -|9 9 9 9 - - - -|7 7 7 7 - - - -|8 8 8 8 - - - - right to left
- - - - - - - - 8 9 9 9 9 9 9 9|- - - - - - - - 7 7 7 8 8 8 · · left to right
9 9 9 9 9 9 9 9 - - - - - - - -|8 8 8 8 8 8 8 8 - - - - - - - - right to left
- - - - - - - - - - - - - - - - 9 9 9 9 9 9 9 9 9 9 9 9 9 9 · · left to right
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 - - - - - - - - - - - - - - - - right to left
标记-用于忽略那些必须与下一级相同的部分，不需要复制。在这种情况下，相关切片是
|---------------------------------|
1 7 0 4 0 9 0 7 0 4 5 7 4 3 4 6 3
↓ ↓
9 9 9 9 - - - -|- - - - - - - - 7 7 7 8 8 8 · ·
right to left | left to right
和想要的最大值如所示。真正的最大值就是这两个值中的最大值。
这显然需要 O(n log n) 内存，因为有 log n 个级别，每个级别都需要一整行值（尽管它们可以作为索引来保存 space）。但是，更新可能会花费 O(n) 时间，因为它们可能会传播 - 例如，向其添加 10 会使整个底部 right-to-left 行无效。突变显然同样低效。
O(1) 时间通过回答不同的问题
根据您需要它的上下文，您可能会发现可以截断搜索深度。如果允许您的切片相对于切片的大小有一些余地，则此方法有效。由于切片几何收缩，尽管来自 0:4294967295 的切片需要大量的 22 次迭代，截断为固定数量的 11 次迭代会给出切片的最大值 0:4292870144，差异为 0.05%。这可能是可以接受的。
O(1) 预计时间利用概率
四舍五入可能是可以接受的，但即使是这样，您仍在执行 O(log n) 算法 - 只是使用更小的固定 n。可以在随机分布的数据上做得更好。
考虑森林的一侧。当你向下遍历它时，你看到的数字的分数超过了你没有看到的几何分数。因此，您已经看到最大面值的概率增加了。您可以利用它来发挥自己的优势。
再考虑这一半：
---------------------|
0 7 0 4 5 7 4 3 4 6 3 8 2 4 · ·
7 4 7 4 6* 8 4 ·
7 7 8* 4
7* 8
8
检查完7*后，不要马上遍历到6*。相反，检查其余 all 中最小的 parent，即 8*。仅当此 parent 大于目前为止的最大值时才向下遍历。如果不是，您可以停止迭代。只有更大了才需要继续向下遍历。刚好最大的值是这里的最后一个，所以我们一路向下遍历，但是你可以想象这是不寻常的。
至少有一半的时间你只需要评估第一个三角形，剩下的至少一半你只需要向下看一次，等等。这是一个几何序列，表明平均遍历成本是两次次遍历；更少，如果你考虑到剩余的三角形在某些时候可能小于一半的大小。
在最坏的情况下呢？
最坏的情况发生在非随机树上。最病态的是排序数据：
---------------------|
0 1 2 3 4 5 6 7 8 9 a b c d e f
1 3 5 7 9 b d f
3 7 b f
7 f
f
因为最大值总是在你没见过的范围的片段中，不管你选择哪个片段因此遍历总是O(log n)。不幸的是，排序数据在实践中很常见，这个算法在这里受到了伤害（这个 属性 与其他几个算法共享，比如快速排序）。不过，可以减轻危害。
不死于排序数据
如果每个节点都说明它是排序的，还是反向排序的，那么在到达该节点后您不需要再进行遍历 - 您只需获取子数组中的第一个或最后一个元素即可。
---------------------|
0 1 2 3 4 5 6 7 8 9 a b c d e f
→ → → → → → → →
→ → → →
→ →
→
您可能会发现您的 mostly-sorted 数据具有一些小的随机化，但是，这打破了方案：
---------------------|
0 1 2 3 4 5 6 7 a 9 a b d 0 e f
→ → → → ← → ← →
→ → b f
→ f
f
因此，每个节点在保持排序的同时可以向下移动的最大级别数，以及在哪个方向。然后你跳过那么多迭代。一个例子：
---------------------|
0 1 2 3 4 5 6 7 a 9 a b d 0 e f
→1 →1 →1 →1 ←1 →1 ←1 →1
0 3 5 7 a b d f
→2 →2 →1 →1
3 7 b f
→3 →2
7 f
→3
f
→n 表示如果您向下跳过 n 层，所有节点都将从左到右排序。顶级节点是 →3，因为向下排序了三个级别：0 3 5 7 a b d f。方向很容易用一位编码。因此 mostly-sortedness 处理得很好。
这很容易保持更新，因为每个节点都可以直接从它的 children 计算出它的值。如果他们同意并按他们同意的相同方向排序，则最小距离加一。否则重置为 1 的距离并指向 children 排序的方向。最难的是遍历中的逻辑，看起来有点挑剔。
仍然可以产生需要一直遍历到底层的例子，但是在non-adversarial数据中应该不会频繁出现。
我偶然发现了这个问题的术语：
范围最小查询
不出所料，这是一个经过充分研究的问题，尽管它似乎很难搜索。 Wikipedia gives some solutions 与我的明显不同。
O(1) 时间，特别是 O(n log n) space 解决方案比我的类似方法更有效，因为它允许在 O(log n) 时间内追加，这可能就足够了，而不是可怕的 O(n) 地雷造成的。
其他方法都是渐近体面的，最后的结果特别好。 O(log n) 时间，O(n) space 解决方案在技术上比我的最终结果弱，但 log n 永远不会很大，并且由于其线性扫描，它在搜索上具有更好的常数因子记忆。在这两种情况下附加元素都被摊销 O(1)，维基百科变体在足够小心的情况下做得更好。我希望将块大小设置为固定值并直接应用该算法将是一个实际的胜利。在我的例子中，即使是超过 128 的块大小对于搜索来说也足够快，并且最小化追加开销和 space 开销的常数因子。
最后的恒定时间方法似乎是一个几乎没有实际用途的学术成果。
给定一个值数组，您如何构建一个数据结构来让您快速找到任何连续子数组的最大值？理想情况下，构建此结构的开销应该很小，并且该结构应该允许有效地附加和更改单个元素。
示例数组为 [6, 2, 3, 7, 4, 5, 1, 0, 3]。请求可能是找到从索引 2 到 7（子数组 [3, 7, 5, 1, 0]）的切片的最大值，这将导致 7.
设 n 为数组的长度，k 为切片的长度。
天真，O(log k)，方法
一个明显的解决方案是构建一棵重复给出最大值的成对摘要的树
1 8 4 5 4 0 1 5 6 9 1 7 0 4 0 9 0 7 0 4 5 7 4 3 4 6 3 8 2 4 · ·
8 5 4 5 9 7 4 9 7 4 7 4 6 8 4 ·
8 5 9 9 7 7 8 4
8 9 7 8
9 8
9
这些摘要最多占用O(n) space，并且可以通过使用短索引来有效地存储较低级别。例如，底层可以是位数组。附加和单个突变需要 O(log n) 时间。如果需要，还有许多其他方面需要优化。
所选切片可以拆分为两个切片，拆分在两个三角形之间的边界上。在此示例中，对于给定的切片，我们将这样拆分：
|---------------------------------|
6 9 1 7 0 4 0 9|0 7 0 4 5 7 4 3 4 6 3 8 2 4 · ·
9 7 4 9 | 7 4 7 4 6 8 4 ·
9 9 | 7 7 8 4
9 | 7 8
| 8
在每个三角形中，我们对这些树中的 forest 感兴趣，这些树最低限度地确定了我们实际关心的元素：
|---------------------------------|
1 7 0 4 0 9|0 7 0 4 5 7 4 3 4 6 3
7 4 9 | 7 4 7 4 6
9 | 7 7
| 7
请注意，在这种情况下，左边有两棵树，右边有三棵。树的总数最多为 O(log k)，因为任何给定高度最多有两棵。我们可以用一点bit-math
round_to = (start ^ end).bit_length() - 1
split_point = (end >> height) << height
请注意，Python 的 bit_length 可以在 x86 架构上使用 lzcnt 指令快速完成。相关树位于拆分的每一侧。相关子树的大小编码在这些数字的残差位中：
lhs_residuals = split_point - start
rhs_residuals = end - split_point
bin(lhs_residuals)
# eg. 10010110
# sizes = 10000000
# 10000
# 100
# 10
很难遍历整数的最高有效位，但如果你进行位交换（一个字节交换指令加上一些 shift-and-masks），你就可以通过迭代这个来遍历最低有效位：
new_value = value & (value - 1)
lowest_set_bit = value ^ new_value
value = new_value
遍历左半边和右半边需要 O(log k) 预期时间，因为最多有 2log₂ k 棵树 - 每边一个位。
切线：在 O(1) 时间和 O(n log n) space
中处理残差
O(log k)优于O(log n)，但仍未开创先河。先前尝试的一个有益效果是每一侧的树都是 "attached" 一侧；他们的切片中只有 n 个范围，而任意切片中没有 n² 个范围。您可以通过添加到每个级别的累积最大值来利用它，如下所示：
1 8 4 5 4 0 1 5 6 9 1 7 0 4 0 9 0 7 0 4 5 7 4 3 4 6 3 8 2 4 · ·
- 8|- 5|- 4|- 5|- 9|- 7|- 4|- 9|- 7|- 4|- 7|- 4|- 6|- 8|- 4|- · left to right
8 -|5 -|4 -|5 -|9 -|7 -|4 -|9 -|7 -|4 -|7 -|4 -|6 -|8 -|4 -|· - right to left
- - 8 8|- - 4 5|- - 9 9|- - 4 9|- - 7 7|- - 7 7|- - 6 8|- - · · left to right
8 8 - -|5 5 - -|9 9 - -|9 9 - -|7 7 - -|7 7 - -|8 8 - -|4 4 - - right to left
- - - - 8 8 8 8|- - - - 9 9 9 9|- - - - 7 7 7 7|- - - - 8 8 · · left to right
8 8 5 5 - - - -|9 9 9 9 - - - -|7 7 7 7 - - - -|8 8 8 8 - - - - right to left
- - - - - - - - 8 9 9 9 9 9 9 9|- - - - - - - - 7 7 7 8 8 8 · · left to right
9 9 9 9 9 9 9 9 - - - - - - - -|8 8 8 8 8 8 8 8 - - - - - - - - right to left
- - - - - - - - - - - - - - - - 9 9 9 9 9 9 9 9 9 9 9 9 9 9 · · left to right
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 - - - - - - - - - - - - - - - - right to left
标记-用于忽略那些必须与下一级相同的部分，不需要复制。在这种情况下，相关切片是
|---------------------------------|
1 7 0 4 0 9 0 7 0 4 5 7 4 3 4 6 3
↓ ↓
9 9 9 9 - - - -|- - - - - - - - 7 7 7 8 8 8 · ·
right to left | left to right
和想要的最大值如所示。真正的最大值就是这两个值中的最大值。
这显然需要 O(n log n) 内存，因为有 log n 个级别，每个级别都需要一整行值（尽管它们可以作为索引来保存 space）。但是，更新可能会花费 O(n) 时间，因为它们可能会传播 - 例如，向其添加 10 会使整个底部 right-to-left 行无效。突变显然同样低效。
O(1) 时间通过回答不同的问题
根据您需要它的上下文，您可能会发现可以截断搜索深度。如果允许您的切片相对于切片的大小有一些余地，则此方法有效。由于切片几何收缩，尽管来自 0:4294967295 的切片需要大量的 22 次迭代，截断为固定数量的 11 次迭代会给出切片的最大值 0:4292870144，差异为 0.05%。这可能是可以接受的。
O(1) 预计时间利用概率
四舍五入可能是可以接受的，但即使是这样，您仍在执行 O(log n) 算法 - 只是使用更小的固定 n。可以在随机分布的数据上做得更好。
考虑森林的一侧。当你向下遍历它时，你看到的数字的分数超过了你没有看到的几何分数。因此，您已经看到最大面值的概率增加了。您可以利用它来发挥自己的优势。
再考虑这一半：
---------------------|
0 7 0 4 5 7 4 3 4 6 3 8 2 4 · ·
7 4 7 4 6* 8 4 ·
7 7 8* 4
7* 8
8
检查完7*后，不要马上遍历到6*。相反，检查其余 all 中最小的 parent，即 8*。仅当此 parent 大于目前为止的最大值时才向下遍历。如果不是，您可以停止迭代。只有更大了才需要继续向下遍历。刚好最大的值是这里的最后一个，所以我们一路向下遍历，但是你可以想象这是不寻常的。
至少有一半的时间你只需要评估第一个三角形，剩下的至少一半你只需要向下看一次，等等。这是一个几何序列，表明平均遍历成本是两次次遍历；更少，如果你考虑到剩余的三角形在某些时候可能小于一半的大小。
在最坏的情况下呢？
最坏的情况发生在非随机树上。最病态的是排序数据：
---------------------|
0 1 2 3 4 5 6 7 8 9 a b c d e f
1 3 5 7 9 b d f
3 7 b f
7 f
f
因为最大值总是在你没见过的范围的片段中，不管你选择哪个片段因此遍历总是O(log n)。不幸的是，排序数据在实践中很常见，这个算法在这里受到了伤害（这个 属性 与其他几个算法共享，比如快速排序）。不过，可以减轻危害。
不死于排序数据
如果每个节点都说明它是排序的，还是反向排序的，那么在到达该节点后您不需要再进行遍历 - 您只需获取子数组中的第一个或最后一个元素即可。
---------------------|
0 1 2 3 4 5 6 7 8 9 a b c d e f
→ → → → → → → →
→ → → →
→ →
→
您可能会发现您的 mostly-sorted 数据具有一些小的随机化，但是，这打破了方案：
---------------------|
0 1 2 3 4 5 6 7 a 9 a b d 0 e f
→ → → → ← → ← →
→ → b f
→ f
f
因此，每个节点在保持排序的同时可以向下移动的最大级别数，以及在哪个方向。然后你跳过那么多迭代。一个例子：
---------------------|
0 1 2 3 4 5 6 7 a 9 a b d 0 e f
→1 →1 →1 →1 ←1 →1 ←1 →1
0 3 5 7 a b d f
→2 →2 →1 →1
3 7 b f
→3 →2
7 f
→3
f
→n 表示如果您向下跳过 n 层，所有节点都将从左到右排序。顶级节点是 →3，因为向下排序了三个级别：0 3 5 7 a b d f。方向很容易用一位编码。因此 mostly-sortedness 处理得很好。
这很容易保持更新，因为每个节点都可以直接从它的 children 计算出它的值。如果他们同意并按他们同意的相同方向排序，则最小距离加一。否则重置为 1 的距离并指向 children 排序的方向。最难的是遍历中的逻辑，看起来有点挑剔。
仍然可以产生需要一直遍历到底层的例子，但是在non-adversarial数据中应该不会频繁出现。
我偶然发现了这个问题的术语：
范围最小查询
不出所料，这是一个经过充分研究的问题，尽管它似乎很难搜索。 Wikipedia gives some solutions 与我的明显不同。
O(1) 时间，特别是 O(n log n) space 解决方案比我的类似方法更有效，因为它允许在 O(log n) 时间内追加，这可能就足够了，而不是可怕的 O(n) 地雷造成的。
其他方法都是渐近体面的，最后的结果特别好。 O(log n) 时间，O(n) space 解决方案在技术上比我的最终结果弱，但 log n 永远不会很大，并且由于其线性扫描，它在搜索上具有更好的常数因子记忆。在这两种情况下附加元素都被摊销 O(1)，维基百科变体在足够小心的情况下做得更好。我希望将块大小设置为固定值并直接应用该算法将是一个实际的胜利。在我的例子中，即使是超过 128 的块大小对于搜索来说也足够快，并且最小化追加开销和 space 开销的常数因子。
最后的恒定时间方法似乎是一个几乎没有实际用途的学术成果。