algorithm - Fenwick树与段树

Question

我需要计算数组范围内的总和，因此我遇到了 Segment Tree 和 Fenwick Tree，我注意到这两种树都以相同的渐近运行时间进行查询和更新。我做了更多的研究，这两种数据结构似乎以相同的速度完成所有事情。两者都具有线性内存使用量(段树使用量是其两倍)。
除了运行时间/内存和实现中的恒定因素之外，还有什么理由让我选择一个而不是另一个？
我正在寻找一个客观的答案，例如某些操作比另一个更快，或者可能某个限制另一个没有。
我看到了另外 2 个关于此的 StackOverflow 问题，但答案只是描述了这两种数据结构，而不是解释何时一个可能比另一个更好。

Answer 1

我read this on Quora .希望你觉得它有用。

有些事情段树可以做而 BIT 不能做 :BIT 本质上适用于累积数量。当需要区间 [i..j] 的累积量时，它是 [1...j] 和 [1...i-1] 的累积量之间的差值。这只是因为加法有一个逆运算。如果操作是不可逆的(例如 max)，则无法执行此操作。另一方面，线段树上的每个区间都可以作为不相交区间的并集找到，不需要逆运算

A BIT 只需要段树一半的内存 :如果您有自虐的内存限制，您几乎无法使用 BIT

虽然BIT和段树操作都是O(log(n))，但是段树操作有一个更大的常数因子 : 这在大多数情况下应该无关紧要。但同样，如果您有自虐的时间限制，您可能希望从段树切换到 BIT。如果 BIT/Segment 树是多维的，那么常数因子可能会成为一个更大的问题。