什么是树状数组？

基本的树状数组是一种支持区间查询和单点修改的结构，而且这两种操作的时间复杂度均为 $O(\log n)$，是非常优秀的。

引入

现在有一个数组 $a[1\dots n]$，要求它的前缀和，我们要求比正常 $O(n)$ 更快的方法，应该如何去做？

树状数组就是干这个的。具体地，树状数组 $c[n]$ 的每个元素都管辖了一部分 $a$ 的区间和，通过对树状数组的元素作加减操作，即可得到想要的区间和。那么，该如何划分管辖的区域？这里请出我们的 $\text{lowbit}$ 函数：

• 关于 $\text{lowbit}$ 函数

有了 $\text{lowbit}$，我们就得到了 $c[i]$ 的管辖范围：从 $i$ 开始，向前 $\text{lowbit}(i)$ 的长度，即 $[i-\text{lowbit}(i)+1,~i]$，如图：

区间查询

现在可以解决先前的问题了。不妨先看特殊情况，比如 $a[1\dots7]$ 的前缀和，我们先求出 $c_7$，而 $c_7$ 只管辖 $a_7$，则继续往前，$c_6$ 管辖 $a[5\dots6]$，继续往前，$c_4$ 管辖 $a[1\dots4]$，至此，前缀和就是 $c_4+c_6+c_7$。

我们发现，往前跳的时候，只要跳到现在区间的左端点再左一位，就又“补上”了一部分区间和，不断跳下去直到 $c_0=0$，我们就得到了区间和，而跳跃距离正好是 $\text{lowbit}(i)$，据此，我们终于可以得到求 $a[1\dots n]$ 前缀和的代码：

int getsum(int x) // a[1...x] 的前缀和
{
	int ans = 0;
	while (x > 0) {
		ans += c[x]; // 跳跃时获取区间和
		x -= lowbit(x); // 向前跳 lowbit(x) 个单位
	}
	return ans;
}

要求 $a[m\dots n]$ 的区间和，只需要 $\text{getsum}(n)-\text{getsum}(m-1)$ 即可。

单点修改

有了这个结构我们也可以进行单点修改，但是要对每一个覆盖了这个点的区间进行修改。

该如何知道哪些区间包含了这个点？先推导几个结论：