树状数组与线段树的比较

Question

我需要在一个数组的范围内计算总和，于是我了解了线段树和树状数组（Fenwick Tree），发现这两个数据结构都具有相同的渐进运行时间来查询和更新。我进行了更多的研究，发现这两个数据结构可以以相同的速度完成所有操作。两者都具有线性的内存使用（线段树的内存使用量是树状数组的两倍）。

除了运行时间/内存中的常数因素和实现之外，是否有任何理由让我选择其中一个？

我正在寻找客观的答案，例如在一种数据结构上比另一种快的某些操作，或者可能存在一种限制而另一种不存在。

我看到 StackOverflow 上有两个相关问题，但答案只是描述了这两个数据结构，而没有解释何时应该使用其中一个。

- Will Kanga

Answer 1

我在Quora上读到了这篇文章。希望你会发现它有用。

1. 线段树可以做的事情比树状数组多：树状数组基本上是使用累积量。当需要区间[i..j]的累计数量时，它被找到作为[1...j]和[1...i-1]的累计数量之差。这仅适用于加法具有反向操作的情况。如果操作是不可逆的（例如max），则无法执行此操作。另一方面，线段树上的每个区间都可以作为不相交区间的并集找到，并且不需要反向操作。
2. 树状数组只需要一半的内存作为线段树：在具有虐待症式内存限制的情况下，您几乎只能使用树状数组。
3. 尽管树状数组和线段树操作都是O(log(n))，但线段树操作具有更大的常数因子：对于大多数情况，这不应该成为问题。但是，如果您有虐待症时间限制，您可能需要从线段树切换到树状数组。如果BIT /线段树是多维的，则常数因子可能会成为更大的问题。

- Shridhar R Kulkarni

---

因此，渐近地（即忽略常数因子），线段树比树状数组严格更好？树状数组在渐近意义下能比线段树更快地完成某些任务吗？ - Will Kanga

你一直在谈论BITs，而OP问的是Fenwick Trees。BITs和Fenwick Trees是一回事吗？如果是这样，就需要说明。 - user3724404

通常每个人都知道这个，但对于不知道的人来说，你的评论会很有帮助。祝学习愉快！ - Shridhar R Kulkarni

@user3724404 是的，BIT和Fenwick树是同一种东西。 - manjy

Answer 2

我在 cp-Algorithm 上找到了一些内容，可能对您有所帮助。

线段树（Segment tree）-

• 每次查询的时间复杂度为O(logN)
• 预处理的时间复杂度为O(N)
• 优点：时间复杂度好。
• 缺点：代码量较大，相比其他数据结构。

Fenwick 树（Fenwick tree）-

• 每次查询的时间复杂度为O(logN)

• 预处理的时间复杂度为O(NlogN)

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

• 缺点：Fenwick 树只适用于L=1的查询，无法解决许多问题。

- Harsh Hitesh Shah

---

Fenwick树可以在O(N)时间内构建。不必对每个条目调用更新，只需遍历每个元素并将数组的值更新为其直接父节点即可。 我们可以通过计算R和使用计算出的L的逆函数来使用Fenwick树，即使L != 1也可以。例如，如果求和是函数，则您可以找到R和L的结果并将L的结果从R中减去以获得答案。 - Yogesh

你提到的 L = 1 是什么意思？ - Brainless

@Brainless，L是查询范围的最左边元素，R是最右边的元素。他暗示Fenwick树仅在查询[1，x]范围内的值时才有效，这是错误的，因为您仍然可以通过计算[1，x]的结果并从中减去[1，n-1]的值来推导出每个查询[n，y]（假设n<y）。 - Ajna

Answer 3

评论Harsh Hitesh Shah的回答： 最后一个反对使用Fenwick树的观点，在一般情况下是不成立的。 通过反例证明： 假设我们有一个用于前缀和的Fenwick树，函数query（x）返回从第一个索引1开始到包括索引x的前缀和。 如果我们想要计算某个区间[L，R]的总和，其中1≤L≤R≤N，则可以取query（R）-query（L-1）。

- e p

Answer 4

一些附加信息:

• 线段树也可以隐式存储(就像堆)，这将占用2n的空间。
• 树状数组是一种在线数据结构，意味着您可以像操作数组一样向末尾添加元素，并且仍然可以正常工作。 线段树默认情况下没有此属性。 如果您隐式存储它们，则可以通过将线段树的大小加倍（就像摊销O(1)数组一样）以分摊复杂度O(log(n))实现追加和前置操作。 您需要研究线段树在内存中的外观，然后相应地放置新的空间（不能只在一端放置所有额外的空间）。 请记住，由于线段树已经占用了2n的空间，因此每次扩大数组后，现在的使用空间为4n。
• 树状数组更快且极其简单易懂。渐近界限相等，但最基本的查询和更新代码几乎没有分支、非递归并且使用的操作非常少。 线段树版本可以几乎达到这么快，但需要额外的努力。值得庆幸的是，只有在非常大的输入情况下才会出现这种情况，因为隐式存储线段树具有良好的空间局部性，相对于存储指针而言，它使其效率更高。
• 据我所知，树状数组无法在log(n)时间内计算逆序查询;例如，如果我们正在存储部分总和，并且我想知道哪个索引i评估为部分总和s，则需要log(n)^2。 这个过程对于线段树来说是微不足道的log(n)。
• 线段树可以执行各种其他查询，其中许多在树状数组上不可能执行。 当然，您需要付出额外的存储成本2n来获得这种额外的灵活性。

编辑：您确实可以在log(n)时间内计算此查询！这是我的实现：

def find(self, s):
    b = 1
    while b < len(bit):
        b <<= 1
    b >>= 1
    index = 0
    cur = 0
    while b > 0:
        if bit[index + b] + cur <= s:
            index += b
            cur += bit[index]
        b >>= 1
    return (index, cur)

这将返回最接近目标部分和（始终<=目标）的索引和总和。我不认为这适用于BIT中的负数。

优秀的线段树介绍：https://cp-algorithms.com/data_structures/segment_tree.html

- Asad-ullah Khan