arrays - 为什么/何时我们使用段树进行范围最小查询？

Question

我读到，为了使用段树实现范围最小查询，预处理需要 O(n) 时间，为每个查询找到解决方案需要 O(log(n)) 时间。它也需要额外的空间。

相反，如果我们简单地为数组的某个子数组找到最小值，我们可以在 O(n) 中找到它。

那么，我们为什么要使用段树实现呢？物流有哪些？
是关于常数因子吗？
当段树特别有用时，是否存在特殊情况？

Answer 1

有许多结构可以让您在亚线性时间内对数组进行大量操作。我将它们分为两类：固定的和动态的。

固定结构拥有出色的查询运行时间，但不支持数组更新。RMQ 允许您在恒定时间查询（使用O(n log n)预计算和内存）中执行范围 min/max/gcd，但不支持更新。前缀总和可让您在恒定时间内获得范围总和，但也不支持更新。这两个都是固定结构的示例，因为数组中的更新需要对结构进行近乎完整的重新计算。

为了支持更广泛的操作，动态结构会牺牲更多的内存和时间。BIT/Fenwick 树可让您在O(log n)每次操作中进行点更新、范围总和。这种结构的开销比段树低，并且在您只需要这些操作的情况下很有用。然后当然是：Segment Trees。

段树确实支持范围 min/max/gcd 查询，例如 RMQ。它们还支持范围求和，例如 BIT / 前缀求和。这些查询支持更新，因此您可以像上面那样进行点更新。然而，只要有一点聪明，他们可以做的更多！段树很容易修改以支持范围更新（为范围内的每个元素添加/减去一个值）。它们可以支持点集和范围集查询（将范围内的所有值设置为所需值）。它们可以支持范围位运算（AND、OR、XOR）。它们可以支持范围计数（计算预定所需数字的数量），或者返回查询值的第一个/最后一个索引。

这些只是可以对段树进行简单修改以支持的一些操作。可能性非常广泛，这就是为什么段树对于如此多的应用程序如此有用的结构。了解他们非常重要，练习如何让他们的力量解决你的问题是一项非常有用的技能。