Fenwick树与段树

Question

我需要计算数组范围内的总和，所以我遇到了 Segment Tree 和 Fenwick Tree，我注意到这两种树都以相同的渐近运行时间进行查询和更新。我做了更多的研究，这两种数据结构似乎以相同的速度完成所有事情。两者都具有线性内存使用量（段树使用量是其两倍）。

除了运行时间/内存和实现中的恒定因素之外，还有什么理由让我选择一个而不是另一个？

我正在寻找一个客观的答案，例如某些操作比另一个更快，或者可能某个限制另一个没有。

我看到了另外 2 个关于此的 StackOverflow 问题，但答案只是描述了这两种数据结构，而不是解释何时一个可能比另一个更好。

Answer 1

我在 Quora 上读到了这个。希望你觉得它有用。

1. 有些事情是段树可以做的，但 BIT 不能：BIT 本质上与累积数量一起工作。当需要区间 [i..j] 的累积量时，可以找到 [1...j] 和 [1...i-1] 的累积量之间的差值。这只是因为加法有一个逆运算。如果操作是不可逆的（例如 max），则无法执行此操作。另一方面，线段树上的每个区间都可以作为不相交区间的并集找到，不需要逆运算
2. 一个BIT只需要一半的内存段树：在你有自虐内存限制的情况下，你几乎坚持使用位
3. 虽然 BIT 和段树操作都是 O(log(n))，但段树操作有一个更大的常数因子：这在大多数情况下应该无关紧要。但同样，如果您有自虐的时间限制，您可能希望从段树切换到 BIT。如果 BIT/Segment 树是多维的，那么常数因子可能会成为一个更大的问题。

Answer 2

我在cp-Algorithm上找到了一些 可能对你有帮助的东西。

线段树-

• 在 O(logN) 内回答每个查询
• 预处理在 O(N) 内完成
• 优点：时间复杂度好。
• 缺点：与其他数据结构相比，代码量更大。

芬威克树-

• 在 O(logN) 内回答每个查询

• 预处理在 O(NlogN) 内完成

• 优点：代码最短，时间复杂度好

• 缺点：Fenwick树只能用于L=1的查询，因此不适用于很多问题。

Answer 3

对 Harsh Hitesh Shah 答案的评论：反对使用 Fenwick 树的最后一点通常不成立。通过反例证明：假设我们有一个用于前缀和的 Fenwick 树，函数 query(x) 返回从第一个索引 1 开始到包括索引 x 的前缀和。如果我们想计算某个区间 [L, R] 的总和，且 1 < L <= R <= N，我们可以采用 query(R)-query(L-1)。