分域树与线段树

Question

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

除了 running-time/memory 和实施中的常数因素外，还有什么理由让我选择一个而不是另一个？

我正在寻找一个 objective 答案，比如某个操作比另一个更快，或者一个有一些限制而另一个没有。

我看到了另外 2 个 Whosebug 问题，但答案只是描述了两种数据结构，而不是解释什么时候一个可能比另一个更好。

Answer 1

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

有些事情线段树可以做而 BIT 不能：BIT 本质上是处理累积量。当需要区间 [i..j] 的累积数量时，它是 [1...j] 和 [1...i-1] 的累积数量之间的差值。这之所以有效，是因为加法有一个逆运算。如果操作是 non-invertible（例如 max），则不能执行此操作。另一方面，线段树上的每个区间都可以作为不相交区间的并集找到，不需要逆运算
A BIT 只需要线段树一半的内存：如果你有自虐式内存限制，你几乎无法使用 BIT
虽然BIT和线段树操作都是O(log(n))，但线段树操作有一个更大的常数因子：对于大多数情况来说这应该无关紧要。但是再一次，如果你有自虐的时间限制，你可能想要从线段树切换到 BIT。如果 BIT/Segment 树是多维的，常数因子可能会成为一个更大的问题。

Answer 2

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

线段树-

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

分域树 -

在 O(logN)
中回答每个查询
预处理时间复杂度为 O(NlogN)
优点：代码最短，时间复杂度好
缺点：分域树只能用于L=1的查询，所以是不适用于很多问题。

Answer 3

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

Answer 4

一些附加信息：

线段树可以存储也可以隐式存储（就像堆一样），这会占用2n space
分域树是一种在线数据结构，意味着你可以在末尾添加元素，就像数组一样，它仍然有效。线段树默认没有这个属性。如果隐式存储它们，则可以通过将线段树的大小加倍（就像分摊 O(1) 数组一样）在分摊 O(log(n)) 中实现追加和前置操作。你需要研究线段树在内存中是什么样子，然后相应地放置新的space（你不能只把所有额外的space放在一端）。请记住，由于线段树已经占用 2n space，每次将数组加倍时，您现在就有 4n space 用法
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)

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

好的线段树写法：https://cp-algorithms.com/data_structures/segment_tree.html

分域树与线段树

Fenwick tree vs Segment tree

algorithm

tree

segment-tree

fenwick-tree