树状数组是用来实现单点查询，区间修改的数据结构，虽然功能上可以被线段树完全覆盖，但是容易实现．

基础树状数组#

构造#

我们让树状数组 c 的每一项 c[i] 都存储以 i 为最终位置，以 lowbit(i) 为长度的区间中所有数的和，即 c[i] 存储区间 $[i-lowbit(i)+1, i]$．

例如，一个 16 个元素的数组，其树状数组的管辖区间示意如下：（摘自 oi-wiki ↗）

如果写成二进制，更直观地：

令 $i$ 的二进制表示中，从右起第一个 1 位于第 $k$ 位（即 $lowbit(i) = 2^{k-1}$），则 $c[i]$ 管辖的区间由其本身 $i$ 和所有满足以下条件的正整数 $m$ 组成：

$m$ 的二进制中，第 $k$ 位及比 $k$ 更高的所有位与 $i$ 对应相等，低于第 $k$ 位的部分可以是任意值．

例：对于 $i=88$，二进制为 101 1000，从右起第一个 1 在第 4 位．

因此 $c[88]$ 存储的数为所有形如 101 xxxx 但实际数值不超过 $88$ 的正整数——即固定高三位 101，低四位从 0000 变到 1000，对应区间 $[81, 88]$．

根据二进制知识可知，lowbit(i) = i & -i．

查询操作#

想要对区间 $[l, r]$ 查询，只需要知道区间 $[1,l-1]$ 和区间 $[1, r]$ 的和，之后用后者减去前者即可．

如何进行前缀查询呢？

例如，我想要查询区间 $[1, 7]$，先看 $c[7]$，能管辖 $[7,7]$，那 6 及之前的怎么办呢？$c[i]$ 肯定包含 $i$ 的，于是找到 $c[6]$，能管辖 $[5,6]$，同样的，那 4 及之前的怎么办呢，再看到 $c[4]$，能管辖 $[1,4]$，不剩了．

再例如，我想要查询区间 $[1, 5]$，先看 $c[5]$，能管辖 $[5,5]$，于是再找到 $c[4]$，能管辖 $[1,4]$，不剩了，故答案为 $c[4]+c[5]$．

一般的，我想要查询区间 $[1, n]$，先看 $c[n]$，发现 $c[n]$ 所能够管辖到的最小值为 $n-lowbit(n)+1$，在将 $c[n]$ 加和到 $ans$ 中后，原问题就转化为查询区间 $[1,n-lowbit(n)]$，边界条件是 $[1,0] = 0$．

时间复杂度 $O(\log n)$．

// 查询区间[1,ed]
int query(int ed) {
	int ans = 0;
	for (int i = ed; i >= 1; i -= i & -i) {
		ans += c[i];
	}
	return ans;
}
// 查询区间[l,r]
int query(int l, int r) {
	return query(r) - query(l - 1);
}

修改操作#

我们现在尝试修改序列的第 $i$ 项．

我们知道，树状数组是一棵树的形态，因此，修改一个元素，只需要更新记录这个元素的节点即可．

通过观察上图，所有被影响的节点会组成一条链的形状，且对于节点 $a[i]$，最底端（即下标最小）的节点为 $c[i]$．只需要找出 $c[i]$ 及所有的祖先节点，将它们都同步进行更改即可．

注意到，节点 $c[i]$ 的父节点总是 $c[i+lowbit(i)]$．（节点 $c[i]$ 的父节点为 $i$ 最小的、真包含 $c[i]$ 的节点）

因此，得出修改操作的一般步骤：

1. 令 $k$ 初始化为 $i$
2. 修改 $c[k]$
3. 将 $k$ 设定为 $k+lowbit(k)$，若 $k\leq n$，回到步骤 2

时间复杂度 $O(\log n)$．

void add(int t, int k) {
	for (int i = t; i <= n; i += i & -i) {
		c[i] += k;
	}
}

建树#

一般来说，建树只需要转化为 $n$ 次单点增加就可以了．时间复杂度 $O(n\log n)$．

但是有没有 $O(n)$ 建树的方法呢？

前面提到，$c[i] = sum\{a_i | i \in [i-lowbit(i)+1, i]\}$，可以使用前缀和优化．

for (int i = 1; i <= n; i++) {
	cin >> a[i];
	sum[i] = sum[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) {
	c[i] = sum[i] - sum[i - (i & -i)];
}

标程#

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 100;

int n, m, c[N], a[N], sum[N];

class Tree {
public:
	int query(int ed) {
		int ans = 0;
		for (int i = ed; i >= 1; i -= i & -i) {
			ans += c[i];
		}
		return ans;
	}
	int query(int l, int r) {
		return query(r) - query(l - 1);
	}
	void add(int t, int k) {
		for (int i = t; i <= n; i += i & -i) {
			c[i] += k;
		}
	}
};

int main() {
	cin >> n >> m;
	Tree tree;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
	}
	for (int i = 1; i <= n; i++) {
		c[i] = sum[i] - sum[i - (i & -i)];
	}
	for (int i = 1; i <= m; i++) {
		int op, x, k;
		cin >> op >> x >> k;
		if (op == 1)
			tree.add(x, k);
		else
			cout << tree.query(x, k) << endl;
	}
	return 0;
}

树状数组变体#

如果需要单点查询，区间修改，又该怎么做呢？

很简单，只要使用差分来维护就可以了．

树状数组的主体不用改变，在建树时，由维护数组值改为维护差分值．

for (int i = 1; i <= n; i++) {
	cin >> a[i];
	tree.add(i, a[i] - a[i - 1]);
}

对于查询第 $x$ 项，等同于区间查询差分数组 $[1, x]$．

cin >> x;
cout << tree.query(1, x) << endl;

对于区间修改，设第 $k_1$ 到 $k_2$ 项增加 $x$，等同于 $c[k_1]$ 增加 $x$，$c[k_2+1]$ 减少 $x$．

cin >> x >> y >> k;
tree.add(x, k);
tree.add(y + 1, -k);

标程#

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 100;

int n, m, c[N], a[N], sum[N];

class Tree {
public:
	int query(int ed) {
		int ans = 0;
		for (int i = ed; i >= 1; i -= i & -i) {
			ans += c[i];
		}
		return ans;
	}
	int query(int l, int r) {
		return query(r) - query(l - 1);
	}
	void add(int t, int k) {
		for (int i = t; i <= n; i += i & -i) {
			c[i] += k;
		}
	}
};

int main() {
	cin >> n >> m;
	Tree tree;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		tree.add(i, a[i] - a[i - 1]);
	}
	for (int i = 1; i <= m; i++) {
		int op, x, y, k;
		cin >> op;
		if (op == 1) {
			cin >> x >> y >> k;
			tree.add(x, k);
			tree.add(y + 1, -k);
		}
		else {
			cin >> x;
			cout << tree.query(1, x) << endl;
		}
	}
	return 0;
}