14

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

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

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

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

4

4 回答 4

31

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

  1. 段树可以做一些事情，但 BIT 不能： BIT 本质上适用于累积量。当需要区间 [i..j] 的累积量时，它是 [1...j] 和 [1...i-1] 的累积量之间的差。这仅是因为加法具有逆运算。如果操作是不可逆的（例如 max），则不能这样做。另一方面，线段树上的每个区间都可以作为不相交区间的并集找到，不需要逆运算
  2. BIT 只需要段树一半的内存：在您有自虐内存限制的情况下，您几乎无法使用 BIT
  3. 尽管 BIT 和段树操作都是 O(log(n))，但段树操作有一个更大的常数因子：这对于大多数情况来说都无关紧要。但是再一次，如果您有受虐的时间限制，您可能希望从分段树切换到 BIT。如果 BIT/Segment 树是多维的，则常数因子可能会成为更大的问题。
于 2020-10-04T04:49:44.757 回答
5

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

段树-

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

芬威克树-

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

  • 在 O(NlogN) 中完成的预处理

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

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

于 2021-02-03T12:02:44.357 回答
3

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

于 2021-03-13T00:45:00.203 回答
1

一些附加信息：

  • 段树可以存储也可以隐式存储（就像堆一样），这会占用2n空间
  • Fenwick 树是一种在线数据结构，这意味着您可以将元素添加到末尾，就像数组一样，它仍然可以工作。默认情况下，段树没有此属性。O(log(n))如果您隐式存储它们，则可以通过将段树的大小加倍（就像摊销O(1)数组一样）来实现摊销的追加和前置操作。您需要研究段树在内存中的样子，然后相应地放置新空间（您不能只将所有额外空间放在一端）。请记住，由于段树已经占用了2n空间，因此每次将数组加倍时，您现在都有4n空间使用
  • Fenwick 树的实现速度更快且极其简单。渐近界是等价的，但最基本的查询和更新代码几乎是无分支的、非递归的，并且使用的操作很少。段树版本的制作速度几乎一样快，但这确实需要额外的努力。值得庆幸的是，这仅在非常大的输入中很重要，因为隐式存储段树具有出色的空间局部性，与存储指针相比，这给了它一个很好的提升
  • Fenwick 树无法计算逆查询log(n)（据我所知）；也就是说，例如，如果我们要存储部分总和，并且我想知道什么索引i评估为部分总和s，那将需要log(n)^2. 这个过程log(n)对于线段树来说是微不足道的
  • 分段树可以执行多种其他查询，其中许多在 Fenwick 树上是不可能的。当然，您要为这种额外的灵活性付出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

于 2021-03-21T08:06:08.407 回答