树状数组，线段树，傻傻分不清楚？

前面我们讲了线段树以及线段树是如何高效解决某些区间问题的。不少人也听说过树状数组，据说树状数组也可以解决一些区间问题。那么树状数组和线段树有什么区别呢？它们又有什么联系呢？本文将带你一探究竟。

对于非竞赛的同学来说，能够使用线段树基本就足够了。但是如果你需要准备一些竞赛，需要掌握竞赛难度的题目的话，树状数组也是必须要掌握的。

相比线段树，树状数组最大的好处就是需要的空间更小，线段树我们需要额外开辟大概 $4*n$ 空间，而树状数组则只需要 $n$，这或许就是某些题目线段树因为内存等原因无法通过，而树状数组可以通过的主要原因。除此之外，树状数组代码实现非常简单，但是它的思想却相对线段树更加复杂和难以想到。

强烈建议大家看完我的线段树文章再来学习树状数组，我的文章也假定你已经具备了线段树的知识！
强烈建议大家看完我的线段树文章再来学习树状数组，我的文章也假定你已经具备了线段树的知识！
强烈建议大家看完我的线段树文章再来学习树状数组，我的文章也假定你已经具备了线段树的知识！

什么是树状数组

树状数组（Fenwick Tree）是一种数据结构，用于高效计算数组的前缀和，进而通过前缀和来计算区间和。当然也可以用于计算区间最大值等指标，原因和线段树类似，具体可以参考我的线段树文章。

前置知识

注意，树状数组先计算前缀和，也就是计算的区间和的左端点是固定的（左端点固定是数组最左端），右端点是变化的。

那么需要计算的区间一共有多少个？答案是 n 个，因为左端点固定，右端点只有 n 个，所以一共有 n 个区间。

那么我们一共维护 n 个区间和吗？当然不是，因为比如一旦修改 nums[0]，那么 n 个区间的结果都需要更新，这样的话，我们还不如直接遍历数组计算区间和。

线段树会对区间进行恰当的拆分，从而使得更新某个元素的时候，最多只需要对 $logn$ 个区间进行更新（查询也是类似的）。比如我们要查询区间 $[1, 5]$ 的和，我们可以拆分成 $[1, 4]$ 和 $[5, 5]$。两个区间的和就是前缀 $[1, 5]$ 的和。

那么划分区间的方法具体是什么呢？这就需要从二进制的角度来看。

二进制角度

比如我们要查询区间 [1,7] 的所有前缀和。

7 的二进制是 111，那么我们可以拆分成长度分别为 0b001(十进制1)，0b010(十进制2)，0b100(十进制4) 这三个区间。具体就是 [1,4] 的长度为 4 的区间, [5,6] 的长度为 2 的区间，以及 [7,7] 这个长度为 1 的区间。

6 的二进制是 110，那么我们可以拆分成长度分别为 0b010(十进制2)，0b100(十进制4) 这两个区间。 具体就是 [1,4] 的长度为 4 的区间，[5,6] 的长度为 2 的区间。（注意这两个区间我们前面已经创建过了，不需要创建了）

5 的二进制是 101，那么我们可以拆分成长度分别为 0b001(十进制1)，0b100(十进制4) 这两个区间。 具体就是 [1,4] 的长度为 4 的区间，[5,5] 的长度为 1 的区间。（注意 [5,5] 是新的关键区间）

4 的二进制是 100，那么我们可以拆分成长度分别为 0b100(十进制4) 这一个区间。 具体就是 [1,4] 的长度为 4 的区间。（注意 [1,4] 前面已经创建过了，不需要创建了）

3 的二进制是 011，那么我们可以拆分成长度分别为 0b001(十进制1)，0b010(十进制2) 这两个区间。 具体就是 [1,2] 的长度为 2 的区间，[3,3] 的长度为 1 的区间。（注意 [1,2] 和 [3,3] 是新的区间）

2 的二进制是 010，那么我们可以拆分成长度分别为 0b010(十进制2) 这一个区间。 具体就是 [1,2] 的长度为 2 的区间。（注意 [1,2] 前面已经创建过了，不需要创建了）

1 的二进制是 001，那么我们可以拆分成长度分别为 0b001(十进制1) 这一个区间。 具体就是 [1,1] 的长度为 1 的区间。（注意 [1,1] 是新的区间）

看出来了吗？就是将 i 拆分为长度和为 i 的若干区间，每个区间的长度就是二进制拆分的结果。

只要这7个区间，我们就能组合出所有的前缀和。 这 7 个区间分别为：

• [1,1]
• [1,2]
• [1,4]
• [3,3]
• [5,5]
• [5,6]
• [7,7]

注意区间一共有 n 个，左端点不是固定的，是可能重合的。而右端点是不重合的，分别是 1-n。

关于为什么，其实有严格的数学证明。感兴趣的可以搜索一下，大家目前只需要先记住即可。

比如要计算 [3,7] 的和，我们可以拆分成 [1,7] 的和减去 [1,2] 的和。而 [1,7] 的和就是 [1,4]+[5,6]+[7,7] 的和，[1,2] 的和就是 [1,2] 的和。

计算其他区间的和也是类似的，只要拆分成若干个关键区间的和即可，大家可以自行找几个例子试试来加深一下印象。

lowbit

为了快速求出区间和，我们可以借助 lowbit。

lowbit是为了获取一个数的二进制中最低位的1对应的值，比如lowbit(10) = 2，因为10的二进制表达是1010，lowbit(10) 取的就是 ob10。再比如lowbit(9) = 1，因为9的二进制表达是1001，lowbit(9) 取的就是 ob1。

知道了什么事 lowbit，下面我们来看下如何计算 lowbit(i)。

lowbit(i) 的计算方法非常简单，就是 i & -i，当然你也可以用其他方式，只不过这种更优雅！

有了 lowbit 铺垫，我们重新来看下前面计算的 n 个区间。用一个公式来说就是：[i−lowbit(i)+1,i]。

具体就是：

• [1-lowbit(1)+1, 1] = [1, 1]
• [2-lowbit(2)+1, 2] = [1, 2]
• [4-lowbit(4)+1, 4] = [1, 4]
• [3-lowbit(3)+1, 3] = [3, 3]
• [5-lowbit(5)+1, 5] = [5, 5]
• [6-lowbit(6)+1, 6] = [5, 6]
• [7-lowbit(7)+1, 7] = [7, 7]

这样计算好 lowbit 之后，我们就可以通过 i -= i & -i 来获取上一个区间的右端点。因为 i 是当前的右端点，那么 i - lowbit(i) + 1 就是其对应的左端点，那么上一个区间的右端点就是 i - lowbit(i)， 即 i - (i & -i)。

有了这两个知识点的铺垫，我们就可以来看树状数组是如何实现的了。

树状数组的基本操作

和线段树类似，树状数组的主要操作有两个：

1. 更新一个元素的值
2. 查询一个区间的和

线段树的查询是对区间一分为二，然后递归查询左右子树，最后合并结果。而树状数组的查询则是通过一个神奇的技巧，通过一个数学公式（就是前面讲的关于 lowbit 计算区间端点的公式）来计算区间和。

建议大家对比线段树进行理解。

那么具体是如何做的呢？大家继续往下看。

树状数组的实现

区间查询

前面讲了关键区间的右端点互不相同。而由于关键区间的右端点互不相同，我们可以把右端点为 i 的关键区间的和保存在 $tree[i]$ 中。

这点和线段树也是类似的，只不过这里我们只需要 n 的长度，而不是线段树的 4*n。

对于 tree[i] 对应的区间的左端点我们可以通过数学公式 i - lowbit(i) + 1 来获取。

假设我们要计算 [1,i] 的和，就先去 tree[i] 里找。而 tree[i] 里存储的是 [i-lowbit(i)+1,i] 的和，因此当我们累加上 tree[i] 后，问题就变成了计算 [1,i-lowbit(i)] 的和。这是一个问题相同，但规模更小的子问题。

我们来看下代码。

def prefixSum(self, i: int) -> int:
    s = 0
    while i:
        s += self.tree[i]
        i -= i & -i # i - lowbit(i) 就是下一个区间的右端点
    return s

区间更新

我们更新 nums[i]，那么所有包含 i 的区间的和都需要更新。我们可以通过 i += i & -i 来获取下一个区间的右端点，进而更新下一个区间的和。

具体细节请看下面的代码注释：

def update(self, index: int, val: int) -> None:
    delta = val - self.nums[index]
    self.nums[index] = val # 先更新 nums[i]
    i = index
    while i < len(self.tree): # 再更新所有包含 nums[i] 的区间
        self.tree[i] += delta
        i += i & -i # 由于 i 是一个区间的右端点，并且左边的都不会包含 i（这个很重要），我们只需要更新后面的区间即可。 而 i + lowbit(i) 就是下一个区间的右端点

树状数组模板

线段树代码已经放在刷题插件上了，公众号《力扣加加》回复插件即可获取。

class BinaryIndexTree:
    __slots__ = 'nums', 'tree'

    def __init__(self, nums: List[int]):
        n = len(nums)
        self.nums = [0] * n
        self.tree = [0] * (n + 1) # n + 1 只是方便计算前缀和，前面加了一个 0，所以总长度就是 n + 1
        for i, x in enumerate(nums):
            self.update(i, x)

    def update(self, index: int, val: int) -> None:
        delta = val - self.nums[index]
        self.nums[index] = val
        i = index + 1 # + 1 的原因同上，也是前面多加了一个 0，导致所有索引都偏移了一位
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i

    def prefixSum(self, i: int) -> int:
        s = 0
        while i:
            s += self.tree[i]
            i -= i & -i
        return s
    def querySum(self, l: int, r: int) -> int:
        if r < l: return 0
        return self.prefixSum(r+1) - self.prefixSum(l)

使用的方式很简单：

• 初始化 BinaryIndexTree 并直接传入一个你想计算指标的数组即可。
• 如何更新原数组的某一项？ 只要调用 update(index, value) 即可，其中 index 和 value 为你想修改的原数组的索引和值。
• 如何查询原数组的区间和？只要调用 querySum(ql, qr) 即可，其中 ql 和 qr 为你想查询的区间的左右端点。

总结

树状数组和线段树都是用于解决区间问题的数据结构，但是树状数组相比线段树书写更加简单，更加节省空间。但是树状数组的思想相对线段树更加复杂，需要一定的数学基础。