树状数组 (Fenwick Tree)：动态前缀和与二进制管辖

树状数组关注的是动态区间求和（支持单点修改与快速区间求和，也可以配合差分处理区间修改）。

树状数组依赖的是二进制拆分（将庞大的区间按 $2$ 的幂次拆分成多段不重叠的子区间）。

树状数组的核心思想是空间层级与管辖范围（利用最低位 1 实现跳跃式的状态转移）。

一、树状数组核心定义与问题背景

前面学 ST 表时，数组是不动的。现在题目开始边改边问，怎么办？先从我们熟悉的前缀和说起。如果数组一旦固定，前缀和能在 $O(1)$ 时间内求出任意区间的和。但是，如果题目要求一边修改某个元素，一边求区间和，普通前缀和每次修改都要重新计算后面的所有项，复杂度退化为 $O(N)$ ，遇到 $10^5$ 的数据必定超时。

树状数组（Binary Indexed Tree, BIT）正是为了解决“动态前缀和”而生的。它巧妙地平衡了修改和查询，把它们的时间复杂度双双压缩到了极速的 $O(\log N)$ 。

通俗理解： “按级别收税的管理体系”。

想象一个公司的管理层级：

1号员工是个普通人，只管自己（负责 1）。
2号是个基层组长，管两个员工（负责 1, 2）。
4号是个部门经理，管四个员工（负责 1, 2, 3, 4）。
8号是个大老板，管八个员工（负责 1 到 8）。

当你改变了 3 号员工的业绩时，你不需要通知所有人，只需要一层层往上汇报给 4 号经理、8 号老板即可（单点修改）。当你需要查前 7 个人的总业绩时，你只需要问 7 号员工（他自己）、6 号组长（管5,6）、4 号经理（管1到4）要数据，拼起来恰好就是前 7 个人的总和（区间查询）。

二、核心原理与推导 (Lowbit & Jurisdiction)

树状数组的一切魔法，都建立在一个极短的位运算函数上：lowbit(x)。别急着背，先用几个数字试一试。

1. `lowbit` 究竟在干什么？

lowbit(x) 的作用是：提取出一个数字的二进制表示中，最低位的 1 和它后面的 0 构成的数值。

举例 6： 6 的二进制是 0110。最低位的 1 在倒数第二位，连带着后面的 0 提取出来就是 0010，对应的十进制就是 2。所以 lowbit(6) = 2。
举例 8： 8 的二进制是 1000。最低位的 1 在最高位，提取出来就是 1000，十进制是 8。所以 lowbit(8) = 8。
举例 5： 5 的二进制是 0101。最低位的 1 在最后，提取出来是 0001，也就是 1。任何奇数的 lowbit 都是 1。

为什么代码写成 x & (-x)？

在计算机中，负数是用“补码”（反码加一）存储的。-x 会把 x 最低位的 1 右边的所有 0 变成进位，最低位的 1 保持不变，而左边的所有位全部取反。两者做“按位与 &”操作时，左边全部清零，只保留了最低位的那个 1。

2. 管辖范围 (Jurisdiction) —— 谁是老板，谁是员工？

数组 tree[x] 到底存了原数组几个数字的和？答案就是 lowbit(x) 个！

tree[x] 管辖的区间严格等于： $[x - lowbit(x) + 1, x]$ 。

我们对应第一节的“公司管理体系”来看看：

8 号（大老板）： lowbit(8) = 8。tree[8] 管 8 个人，存的是原数组 a[1] 到 a[8] 的总和。
6 号（基层组长）： lowbit(6) = 2。tree[6] 管 2 个人，存的是 a[5] 和 a[6] 的和。
5 号（普通员工）： lowbit(5) = 1。tree[5] 只管 1 个人，存的就是 a[5] 自己。

3. 状态转移原理 (核心灵魂)

利用二进制的进位和借位，我们实现了 $O(\log N)$ 的跳跃。

① 向左拼凑（前缀查询 query(7)）：假设我们要查 1 到 7 的和。

7 的二进制是 0111。我们只需根据二进制里的三个 1，拿三个已经算好的大区间拼起来：

第一步： 收集 tree[7] (它只管 a[7])。跳到左侧 $7 - lowbit(7) = 7 - 1 = 6$ 。
第二步： 收集 tree[6] (它管 a[5], a[6])。跳到左侧 $6 - lowbit(6) = 6 - 2 = 4$ 。
第三步： 收集 tree[4] (它管 a[1]~a[4])。跳到左侧 $4 - lowbit(4) = 4 - 4 = 0$ 。结束。

你看！a[7] + [a[5], a[6]] + [a[1]~a[4]] 完美拼成了 1 到 7 的总和，不重不漏！这就是 i -= lowbit(i) 的魔力。

② 向上汇报（单点修改 update(3, x)）：假设原数组 a[3] 增加了 $x$ ，我们需要通知所有管辖范围包含 3 的“领导”。

第一步： tree[3] 包含了 3，自身更新。向汇报给上级 $3 + lowbit(3) = 3 + 1 = 4$ 。
第二步： tree[4] (管1~4，包含3) 更新。汇报给上级 $4 + lowbit(4) = 4 + 4 = 8$ 。
第三步： tree[8] (管1~8，包含3) 更新。汇报给上级 $8 + lowbit(8) = 8 + 8 = 16$ 。

通过 p += lowbit(p)，我们只通知了包含 3 的直接上级，完全避开了无关的节点（比如 5, 6, 7 完全不知道 3 变了），从而实现了极速修改。

树状数组的管辖区间与 lowbit 跳跃

三、标准求解算法与模板 (单点修改，区间查询)

特别注意： 更新的下标从 1 开始！update(0,x) 会因为 lowbit(0)=0 卡在原地。query(0) 则正常返回 0，所以查询左端点为 1 的区间时，照常写 query(r)-query(l-1)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=500005;
int n,m;
int tree[N];
int a[N];

inline int lowbit(int x) {
	return x & (-x);
}

inline void update(int i, int x) {
	for (int  p = i; p <= n; p += lowbit(p))
		tree[p] += x;
}

inline int query(int n) {
	int ans = 0;
	for (int i = n; i >= 1; i -= lowbit(i))
		ans += tree[i];
	return ans;
}

inline int query(int l, int r) {
	return query(r) - query(l - 1);
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i], update(i, a[i]);
	while (m--) {
		int op;
		cin >> op;
		if (op == 1) {
			int i, x;
			cin >> i >> x;
			update(i, x);
		}
		if (op == 2) {
			int l, r;
			cin >> l >> r;
			cout << query(r) - query(l - 1) << "\n";
		}
	}
}

💡 【实战例题 1：树状数组标准默写】 P3374 【模板】树状数组 1

题目大意：已知一个数列，你需要进行两种操作：1. 将某一个数加上 $x$ 。2. 求出某区间 $[l, r]$ 内每一个数的和。

思路引导：这就是动态前缀和的“裸题”。建树的时候，做一次单点修改 update(i, a[i])。查询区间 $[l, r]$ 的和时，利用前缀和相减思想，调用重载函数 query(l, r)，即 query(r) - query(l - 1) 即可。

四、进阶实战：区间修改与单点查询 (差分思想降维)

当题目反过来要求：对一整段区间 $[l, r]$ 都加上 $x$ ，最后问具体位置 $i$ 的值是多少。

如果用 update 把区间里的数挨个改一遍，就要花 $O((r-l+1)\log n)$ ，还是慢。这里请出老朋友——差分数组！

数学降维推导：

设原数组为 $a$ ，差分数组为 $D$ （ $D[i] = a[i] - a[i-1]$ ）。

差分的性质： 原数组中第 $i$ 个数的值 $a[i]$ ，严格等于差分数组 $D$ 的前缀和！
树状数组的融合： 我们用树状数组去维护差分数组。建树时直接算差分：update(i, a[i] - a[i - 1])。
区间修改降为两次单点更新： 对区间 $[l, r]$ 加上 $x$ ，差分数组只需修改两端：update(l, x) 和 update(r + 1, -x)，整体复杂度为 $O(\log N)$ 。
单点查询： 求第 $i$ 个数的值？直接求差分数组的前缀和 query(i) 即可。

拿 a=[2,5,4,7] 看一眼，差分是 D=[2,3,-1,3]。现在给 [2,3] 都加 3，只要把 D[2] 加 3、D[4] 减 3，得到 [2,6,-1,0]。重新累加，就还原出 [2,8,7,7]。中间不用挨个改，这就是两次更新能管一整段的原因。

两份模板外观很像，但问的东西不同：维护原数组时，query(i) 是前缀和；维护差分时，它就是第 i 个数。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=500005;

int n,m;
int tree[N];
int a[N];

int lowbit(int x) {
	return x & (-x);
}

void update(int i, int x) {
	for (int  p = i; p <= n; p += lowbit(p))
		tree[p] += x;
}

int query(int n) {
	int ans = 0;
	for (int i = n; i >= 1; i -= lowbit(i))
		ans += tree[i];
	return ans;
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i], update(i, a[i] - a[i - 1]);
	while (m--) {
		int op;
		cin >> op;
		if (op == 1) {
			int l, r, x;
			cin >> l >> r >> x;
			update(l, x);
			if(r<n) update(r + 1, -x);
		}
		if (op == 2) {
			int i;
			cin >> i;
			cout << query(i) << "\n";
		}
	}
}

💡 【实战例题 2：差分降维打击】 P3368 【模板】树状数组 2

题目大意：已知一个数列，你需要进行两种操作：1. 将区间 $[l, r]$ 内的每个数加上 $x$ 。2. 输出第 $i$ 个数的值。

思路引导：巧妙地把“区间问题”变成了“单点问题”。遇到操作 1，修改差分边界点；遇到操作 2，查前缀和，实现了 $O(\log N)$ 的极速跨越。

五、选学：O(n) 线性建树的巧妙递推

前面提到的建树方式是执行 $n$ 次单点修改，总时间 $O(n \log n)$ 。虽然已经很快，但如果你想追求极致，我们其实可以在 $O(n)$ 时间内完成建树。

核心思路： 既然 tree[i] 管辖它前面的若干个元素，并且我们知道 tree[i] 的直接上级就是 tree[i + lowbit(i)]，那我们完全可以从左到右扫一遍，每个节点算好自己的总和后，直接把自己的业绩“甩”给直接上级。

举个手算的例子：假设原数组为 a = [1, 2, 3, 4]，树状数组的初始大小和 a 一样。

初始 tree 全为 0：tree = [0, 0, 0, 0, 0]。轮到 $i$ 时，先做 tree[i] += a[i]，再向上级汇报，不能提前把 a 整体加进去。
处理 1：先把 tree[1] 加到 1，再向上级 1 + lowbit(1) = 2 汇报，tree[2] 变成 1。
处理 2：先加上 a[2]=2，tree[2] 变成 $1+2=3$ ；再向上级 2 + lowbit(2) = 4 汇报，tree[4] 变成 3。
处理 3：先把 tree[3] 加到 3，再向上级 3 + lowbit(3) = 4 汇报，tree[4] 变成 $3+3=6$ 。
处理 4：再加上自己的 a[4]=4，tree[4] 变成 $6+4=10$ 。上级 8 超出范围，不再上报。最终 tree = [0, 1, 3, 3, 10]。建树完成！没有任何多余的跨步，完美 $O(n)$ 。

// O(n) 线性建树代码片段（可直接替换常规的循环 update）
for (int i = 1; i <= n; i++) {
	tree[i] += a[i]; // 先加上自己
	int fa = i + lowbit(i);
	if (fa <= n) {
		tree[fa] += tree[i]; // 顺手把累加好的业绩汇报给上级
	}
}

六、区间加与区间和：双树状数组的数学拆解

有了差分数组，我们做到了“区间加，单点求值”。但如果题目要求对区间 $[l, r]$ 加上 $x$ ，最后求区间 $[L, R]$ 的总和呢？只用一个差分数组就不够了，因为此时原数组的一个点 $a[i]$ 是差分数组的前缀和；而我们要的是原数组的前缀和，这就变成了“差分数组的前缀和的前缀和”。

数学推导拆解： 设差分数组为 $D$ 。原数组 $a[x] = \sum_{i=1}^x D[i]$ 。我们要求原数组的前 $x$ 项和：

\sum_{i=1}^x a[i] = a[1] + a[2] + \dots + a[x]

把每个

a[i]

拆成差分数组的累加：

= D[1] + (D[1]+D[2]) + \dots + (D[1]+D[2]+\dots+D[x])

观察右边的式子，如果纵向把它们拍扁： $D[1]$ 出现了 $x$ 次， $D[2]$ 出现了 $x-1$ 次…… $D[i]$ 出现了 $x - i + 1$ 次。所以，前 $x$ 项和可以重新组合成：

\sum_{i=1}^x a[i] = \sum_{i=1}^x (x + 1 - i) \times D[i]

我们把括号拆开，分成两部分（提取公因式）：

\sum_{i=1}^x a[i] = (x + 1) \sum_{i=1}^x D[i] - \sum_{i=1}^x (i \times D[i])

结论： 为了快速算这个式子，我们需要维护两个树状数组：

第一个树状数组 t1 维护普通的差分数组 $D[i]$ 。
第二个树状数组 t2 维护 $i \times D[i]$ 。

当对区间 $[l, r]$ 加上 $x$ 时，差分数组 $D[l]$ 增加了 $x$ ，所以 t1 在 $l$ 处加 $x$ ，t2 在 $l$ 处加 $l \times x$ ；同理在 $r+1$ 处分别减去 $x$ 和 $(r+1) \times x$ 即可。

// 区间修改、区间查询模板
// 输入范围：n, m <= 10^5。操作 1 l r x 代表区间加 x，操作 2 l r 代表求区间和。
/*
样例输入:
5 3
1 2 3 4 5
2 1 4
1 2 4 2
2 1 5
样例输出:
10
21
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005;

int n, m;
int a[N];
int t1[N]; // 维护 D[i]
int t2[N]; // 维护 i * D[i]

inline int lowbit(int x) { return x & (-x); }

void add(int i, int x) {
	int v = i * x;
	for (int p = i; p <= n; p += lowbit(p)) {
		t1[p] += x;
		t2[p] += v;
	}
}

// 求 a[1] + ... + a[x]
int query_prefix(int x) {
	int sum1 = 0, sum2 = 0;
	for (int i = x; i >= 1; i -= lowbit(i)) {
		sum1 += t1[i];
		sum2 += t2[i];
	}
	return (x + 1) * sum1 - sum2;
}

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		// O(n log n) 初始化，直接对差分值执行 add
		add(i, a[i] - a[i - 1]);
	}
	while (m--) {
		int op; cin >> op;
		if (op == 1) {
			int l, r, x; cin >> l >> r >> x;
			add(l, x);
			add(r + 1, -x);
		} else {
			int l, r; cin >> l >> r;
			cout << query_prefix(r) - query_prefix(l - 1) << '\n';
		}
	}
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}

七、选学：频次树状数组的倍增跳跃求第 K 小

先修说明： 需要理解桶排序思维与倍增算法（Binary Lifting）。

树状数组还可以当作一个迷你的“值域线段树”来用。如果数组里的值本身不是权重，而是元素出现的频次，前缀和表示的物理意义就变成了：“小于等于某个数的元素一共出现了多少次”。通过在这个频次树状数组上跳跃，我们可以在 $O(\log V)$ 的时间内求出数据流中的第 $K$ 小元素（ $V$ 是值域最大值）。这比“二分查找套树状数组”的 $O(\log^2 V)$ 还要快上一截。

直观例子： 假如当前集合里有 $\{1, 3, 3, 4\}$ 。我们在值域上建树：

值 1：频次 1
值 2：频次 0
值 3：频次 2
值 4：频次 1 此时如果查询前缀和 query(3)，会返回 3（前 3 个数共有 3 个），这说明第 2 小、第 3 小的元素都在值 3 这里。

怎么倍增跳跃？ 我们模仿树状数组的层级，从最大的 $2$ 的幂次步长（比如 65536）开始，尝试往右跳。如果跳过去的管辖范围内的人数积累起来严格小于 $K$ ，我们就放心大胆地跳过去，把这部分人数吃掉；否则，说明步子迈大了，第 $K$ 个人就在里面，我们按兵不动，把步长减半继续试。最后停留的位置就是第 $K$ 小元素的前一个位置。

// 初始为空集合，维护两种操作
// 1 x 表示插入一个非负整数 x；2 k 表示查询当前集合第 k 小元素。
// x 的范围不超过 100000。由于树状数组下标必须 >0，需要全体偏移 +1。
// 查询保证 1 <= k <= 当前集合的元素个数。
/*
样例输入:
4
1 3
1 3
1 1
2 2
样例输出:
3
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 131072; // 值域上限，取 2 的幂次极度方便倍增

int tree[N];

inline int lowbit(int x) { return x & (-x); }

void add(int i, int x) {
	for (int p = i; p < N; p += lowbit(p)) tree[p] += x;
}

// 倍增跳跃求第 k 小
int kth(int k) {
	int pos = 0; // 当前跳到的位置
	int sum = 0; // 当前累计的频次
	
	// 从最高位的 2 的幂次开始尝试，逐步折半
	for (int step = 65536; step >= 1; step /= 2) {
		int next_pos = pos + step;
		// 如果跳过去没超出值域，且积累的人数还不到 k
		if (next_pos < N && sum + tree[next_pos] < k) {
			sum += tree[next_pos]; // 吃掉这一段的人数
			pos = next_pos;        // 放心跳过去
		}
	}
	// 此时 pos 是最后一个满足“累计频次 < k”的位置
	// 所以第 k 小所在的准确位置就是 pos + 1
	return pos + 1;
}

void solve() {
	int m; cin >> m;
	while (m--) {
		int op; cin >> op;
		if (op == 1) {
			int x; cin >> x;
			add(x + 1, 1); // 插入元素，频次 +1，下标加 1 避开 0
		} else if (op == 2) {
			int k; cin >> k;
			cout << kth(k) - 1 << '\n'; // 查出来后把下标偏移减掉
		}
	}
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}

八、写题时怎么选

数组不改，问区间和：普通前缀和最直接。
单点加、区间求和：树状数组维护原数组。
区间加、单点查：树状数组维护差分。
区间加、区间和：双树状数组（第六节）。
区间修改和区间查询都很丰富：下一讲看看线段树。

把 n 个数逐个加入，建树是 $O(n\log n)$ ；第五节的线性建树则是 $O(n)$ 。每次修改、查询 $O(\log n)$ ，空间 $O(n)$ 。

最后别混淆“增加 x”和“改成 x”：update(i,x) 表示增加。若要把原值改成 x，要加的是 x-原值。

树状数组