
树状数组(BIT)作为算法竞赛中处理区间统计的利器,凭借代码简洁、时间效率高的特点,成为了笔试面试和竞赛中的高频考点。而掌握树状数组的核心,就是吃透各类经典模板题 —— 从最基础的单点修改 + 区间查询,到二维的区间修改 + 区间查询,每一道模板题都是对树状数组核心思想的落地实践。 本文将围绕 6 道经典的树状数组模板题展开,涵盖一维基础、一维进阶、二维基础、二维进阶全类型,每道题都包含题目解析、核心思路、完整 C++ 代码、代码详解,从题目到实现一步到位。刷完这 6 道题,你能彻底掌握树状数组的各类用法,面对同类问题再也不用愁!下面就让我们正式开始吧!
题目链接:https://loj.ac/p/130

给定数列 a1,a2,...,an,依次进行 q 个操作,操作分两类:
1 i x:将 ai 加上 x;2 l r:求区间 [l,r] 的所有元素和,即 ∑i=lrai。输入要求:1≤n,q≤106,∣ai∣,∣x∣≤106,1≤l≤r≤n。
输出要求:对于每个第二类操作,输出对应的区间和。
这是树状数组的入门必刷题,直接考察树状数组的两个核心操作:
关键注意:数据范围达到 106,必须用long long存储树状数组和结果,防止 int 溢出;同时需要加速 C++ 的输入输出,避免超时。
#include <iostream>
using namespace std;
// lowbit操作:保留二进制最右边的1
#define lowbit(x) (x & -x)
// 数据范围1e6+10,用long long防止溢出
typedef long long LL;
const int N = 1e6 + 10;
int n, q;
LL tree[N]; // 树状数组存储数组
// 单点修改:位置x增加k
void modify(int x, LL k) {
for (int i = x; i <= n; i += lowbit(i)) {
tree[i] += k;
}
}
// 查询前缀和[1,x]
LL query(int x) {
LL sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
sum += tree[i];
}
return sum;
}
int main() {
// 加速输入输出,处理1e6级数据必备
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
// 初始化树状数组:读入每个数,相当于单点修改加a[i]
for (int i = 1; i <= n; i++) {
LL x;
cin >> x;
modify(i, x);
}
// 处理q次操作
while (q--) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) {
// 操作1:单点修改,位置x加y
modify(x, y);
} else {
// 操作2:区间查询,[x,y]的和 = query(y) - query(x-1)
cout << query(y) - query(x - 1) << endl;
}
}
return 0;
}x & -x 是树状数组的核心,利用补码特性快速获取最右侧的 1;LL 别名long long,树状数组tree和查询结果都用其存储,避免大数溢出;ios::sync_with_stdio(false); cin.tie(0); 关闭 cin 与 stdio 的同步,解除 cin 和 cout 的绑定,大幅提升输入速度;modify,区间查询通过两个前缀和的差得到结果。题目链接:https://loj.ac/p/131

给定数列 a1,a2,...,an,依次进行 q 个操作,操作分两类:
1 l r x:将区间[l,r]的所有元素都加上x;2 i:求ai的当前值。输入要求:1≤n,q≤106,∣ai∣,∣x∣≤106,1≤l≤r≤n。
输出要求:对于每个第二类操作,输出对应的元素值。
树状数组本身不直接支持区间修改,需要结合一维差分思想做转化,这是树状数组的经典进阶用法:
#include <iostream>
using namespace std;
#define lowbit(x) (x & -x)
typedef long long LL;
const int N = 1e6 + 10;
int n, q;
LL tree[N]; // 树状数组维护差分数组
// 单点修改:差分数组位置x增加k
void modify(int x, LL k) {
for (int i = x; i <= n; i += lowbit(i)) {
tree[i] += k;
}
}
// 查询前缀和[1,x] = 原数组a[x]的值
LL query(int x) {
LL sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
sum += tree[i];
}
return sum;
}
// 原数组区间[l,r]加k:转化为差分数组的两次单点修改
void interval_modify(int l, int r, LL k) {
modify(l, k);
if (r + 1 <= n) {
modify(r + 1, -k);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
// 初始化:原数组a[i] = 差分数组前缀和,等价于对[i,i]区间加a[i]
for (int i = 1; i <= n; i++) {
LL x;
cin >> x;
interval_modify(i, i, x);
}
while (q--) {
int op;
cin >> op;
if (op == 1) {
// 操作1:区间修改[L,R]加x
int l, r;
LL x;
cin >> l >> r >> x;
interval_modify(l, r, x);
} else {
// 操作2:单点查询a[x]
int x;
cin >> x;
cout << query(x) << endl;
}
}
return 0;
}interval_modify,增加代码可读性,同时判断r+1≤n,避免下标越界;interval_modify即可完成初始化;query(x),得到的差分数组前缀和就是原数组a[x]的当前值。题目链接:https://loj.ac/p/132

给定数列 a1,a2,...,an,依次进行 q 个操作,操作分两类:
1 l r x:将区间[l,r]的所有元素都加上x;2 l r:求区间[l,r]的所有元素和。输入要求:1≤n,q≤106,∣ai∣,∣x∣≤106,1≤l≤r≤n。
输出要求:对于每个第二类操作,输出对应的区间和。
这是一维树状数组的最高阶模板题,需要结合差分 + 数学公式推导,用两个树状数组分别维护不同的信息,是竞赛中的高频考点。
设原数组为a,差分数组为d(

),原数组的前缀和

,将a[j]用差分数组展开并化简:

令:

则原数组前缀和

,原数组区间和

。
为了代码复用,将树状数组封装为结构体,是竞赛中的常用写法。
#include <iostream>
using namespace std;
#define lowbit(x) (x & -x)
typedef long long LL;
const int N = 1e6 + 10;
int n, q;
LL d[N]; // 差分数组
// 封装树状数组结构体,复用modify和query操作
struct BIT {
LL tree[N];
// 单点修改
void modify(int x, LL k) {
for (int i = x; i <= n; i += lowbit(i)) {
tree[i] += k;
}
}
// 前缀和查询
LL query(int x) {
LL sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
sum += tree[i];
}
return sum;
}
} A, B; // A维护d[k],B维护d[k]*(k-1)
// 原数组区间[x,y]加k,同步更新两个树状数组
void interval_modify(int x, int y, LL k) {
A.modify(x, k);
A.modify(y + 1, -k);
B.modify(x, k * (x - 1));
B.modify(y + 1, -k * y);
}
// 求原数组前缀和[1,i]
LL prefix_sum(int i) {
return (LL)i * A.query(i) - B.query(i);
}
// 求原数组区间和[l,r]
LL interval_query(int l, int r) {
return prefix_sum(r) - prefix_sum(l - 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
// 初始化原数组,构建差分数组d
for (int i = 1; i <= n; i++) {
LL x;
cin >> x;
d[i] += x;
d[i + 1] -= x;
}
// 用差分数组初始化两个树状数组
for (int i = 1; i <= n; i++) {
A.modify(i, d[i]);
B.modify(i, d[i] * (i - 1));
}
while (q--) {
int op, l, r;
cin >> op >> l >> r;
if (op == 1) {
// 操作1:区间[l,r]加k
LL k;
cin >> k;
interval_modify(l, r, k);
} else {
// 操作2:查询区间[l,r]的和
cout << interval_query(l, r) << endl;
}
}
return 0;
}modify和query封装为BIT结构体,A 和 B 两个树状数组直接复用,避免重复代码;(LL)i,避免 int 和 long long 混合运算导致的溢出。题目链接:https://loj.ac/p/133

给出一个n×m的零矩阵A,完成若干操作,操作分两类:
1 x y k:将元素Ax,y自增k;2 a b c d:查询左上角为(a,b)、右下角为(c,d)的子矩阵内所有数的和。输入要求:输入操作直到文件结束,矩阵下标从 1 开始。
输出要求:对于每个第二类操作,输出对应的子矩阵和。
二维树状数组是一维树状数组的二维拓展,核心思路是二维循环,分别对行和列执行 lowbit 操作,本质还是前缀和思想:
#include <iostream>
using namespace std;
#define lowbit(x) (x & -x)
typedef long long LL;
// 二维数组大小根据题目调整,4200满足大部分测试用例
const int N = 4200;
int n, m;
LL tree[N][N]; // 二维树状数组
// 单点修改:(x,y)位置加k
void modify(int x, int y, LL k) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= m; j += lowbit(j)) {
tree[i][j] += k;
}
}
}
// 查询二维前缀和:(1,1) -> (x,y)
LL query(int x, int y) {
LL sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
sum += tree[i][j];
}
}
return sum;
}
// 查询子矩阵和:(a,b) -> (c,d)
LL matrix_query(int a, int b, int c, int d) {
return query(c, d) - query(a-1, d) - query(c, b-1) + query(a-1, b-1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
int op;
while (cin >> op) {
if (op == 1) {
// 操作1:单点修改(x,y)加k
int x, y;
LL k;
cin >> x >> y >> k;
modify(x, y, k);
} else {
// 操作2:查询子矩阵(a,b)-(c,d)的和
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << matrix_query(a, b, c, d) << endl;
}
}
return 0;
}matrix_query严格实现二维前缀和的容斥原理,是二维子矩阵查询的核心,必须牢记;题目链接:https://loj.ac/p/134

给出一个n×m的零矩阵A,完成若干操作,操作分两类:
1 a b c d k:将左上角为(a,b)、右下角为(c,d)的子矩阵内所有数自增k;2 x y:查询元素Ax,y的当前值。输入要求:输入操作直到文件结束,矩阵下标从 1 开始。
输出要求:对于每个第二类操作,输出对应的元素值。
与一维区间修改 + 单点查询的思路一致,结合二维差分思想将区间修改转化为单点修改,是二维树状数组的经典进阶用法。
对原矩阵A的子矩阵(a,b)−(c,d)加k,等价于对二维差分数组diff执行四次单点修改:
原矩阵的单点值Ax,y,等价于二维差分数组diff的前缀子矩阵和(1,1)−(x,y)。
#include <iostream>
using namespace std;
#define lowbit(x) (x & -x)
typedef long long LL;
const int N = 4200;
int n, m;
LL tree[N][N]; // 二维树状数组维护二维差分数组
// 单点修改:(x,y)加k
void modify(int x, int y, LL k) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= m; j += lowbit(j)) {
tree[i][j] += k;
}
}
}
// 查询二维前缀和 = 原矩阵A[x][y]的值
LL query(int x, int y) {
LL sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
sum += tree[i][j];
}
}
return sum;
}
// 原矩阵子矩阵(a,b)-(c,d)加k,转化为四次单点修改
void matrix_modify(int a, int b, int c, int d, LL k) {
modify(a, b, k);
if (d + 1 <= m) modify(a, d + 1, -k);
if (c + 1 <= n) modify(c + 1, b, -k);
if (c + 1 <= n && d + 1 <= m) modify(c + 1, d + 1, k);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
int op;
while (cin >> op) {
if (op == 1) {
// 操作1:子矩阵(a,b)-(c,d)加k
int a, b, c, d;
LL k;
cin >> a >> b >> c >> d >> k;
matrix_modify(a, b, c, d, k);
} else {
// 操作2:单点查询A[x][y]
int x, y;
cin >> x >> y;
cout << query(x, y) << endl;
}
}
return 0;
}matrix_modify,增加代码可读性,同时对边界进行判断,避免下标越界;query(x,y),得到的二维前缀和就是原矩阵Ax,y的当前值;题目链接:https://loj.ac/p/135

给定一个N×M的零矩阵,完成若干操作,操作分两类:
1 a b c d x:将左上角为(a,b)、右下角为(c,d)的子矩阵全部加上x;2 a b c d:查询左上角为(a,b)、右下角为(c,d)的子矩阵内所有数的和。输入要求:输入操作直到文件结束,矩阵下标从 1 开始。
输出要求:对于每个第二类操作,输出对应的子矩阵和。
这是二维树状数组的最高阶模板题,难度比一维更高,需要结合二维差分 + 复杂的数学公式推导,用四个二维树状数组分别维护不同的信息,是竞赛中的难点也是重点。
设原矩阵为A,二维差分数组为d(

),原矩阵的前缀子矩阵和

,将A[x][y]用差分数组展开并化简,最终得到:

其中所有求和的范围都是x=1到i,y=1到j。
同样将二维树状数组封装为结构体,简化代码。
#include <iostream>
using namespace std;
#define lowbit(x) (x & -x)
typedef long long LL;
// 二维数组大小调整为2060,满足题目测试用例
const int N = 2060;
int n, m;
// 封装二维树状数组结构体
struct BIT2D {
LL tree[N][N];
// 单点修改
void modify(int x, int y, LL k) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= m; j += lowbit(j)) {
tree[i][j] += k;
}
}
}
// 二维前缀和查询
LL query(int x, int y) {
LL sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
sum += tree[i][j];
}
}
return sum;
}
} A, B, C, D;
// A: d[x][y]
// B: d[x][y] * x
// C: d[x][y] * y
// D: d[x][y] * x * y
// 四次单点修改,同步更新四个树状数组
void add(int x, int y, LL k) {
A.modify(x, y, k);
B.modify(x, y, k * x);
C.modify(x, y, k * y);
D.modify(x, y, k * x * y);
}
// 原矩阵子矩阵(a,b)-(c,d)加k,转化为四次add操作
void matrix_modify(int a, int b, int c, int d, LL k) {
add(a, b, k);
add(a, d + 1, -k);
add(c + 1, b, -k);
add(c + 1, d + 1, k);
}
// 求原矩阵前缀子矩阵和(1,1)->(x,y)
LL prefix_sum(int x, int y) {
LL res = (LL)(x * y + x + y + 1) * A.query(x, y);
res -= (LL)(y + 1) * B.query(x, y);
res -= (LL)(x + 1) * C.query(x, y);
res += D.query(x, y);
return res;
}
// 求原矩阵子矩阵(a,b)-(c,d)的和,容斥原理
LL matrix_query(int a, int b, int c, int d) {
return prefix_sum(c, d) - prefix_sum(a-1, d) - prefix_sum(c, b-1) + prefix_sum(a-1, b-1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
int op;
while (cin >> op) {
int a, b, c, d;
cin >> a >> b >> c >> d;
if (op == 1) {
// 操作1:子矩阵加k
LL k;
cin >> k;
matrix_modify(a, b, c, d, k);
} else {
// 操作2:查询子矩阵和
cout << matrix_query(a, b, c, d) << endl;
}
}
return 0;
}add,避免重复代码,减少出错概率;long long,防止溢出;matrix_query与二维基础版一致,复用二维前缀和的容斥公式。题号 | 题型 | 维度 | 树状数组数量 | 核心思想 |
|---|---|---|---|---|
1 | 单点修改 + 区间查询 | 一维 | 1 | 直接维护原数组前缀和 |
2 | 区间修改 + 单点查询 | 一维 | 1 | 一维差分 + 维护差分数组 |
3 | 区间修改 + 区间查询 | 一维 | 2 | 一维差分 + 数学推导 + 双数组维护 |
4 | 单点修改 + 子矩阵查询 | 二维 | 1 | 二维前缀和 + 双重循环 |
5 | 区间修改 + 单点查询 | 二维 | 1 | 二维差分 + 四次单点修改 |
6 | 区间修改 + 子矩阵查询 | 二维 | 4 | 二维差分 + 数学推导 + 四数组维护 |
long long,尤其是数据范围≥1e5 的情况,避免 int 溢出;ios::sync_with_stdio(false); cin.tie(0);,否则会超时;树状数组的模板题看似繁多,实则核心思想高度统一 ——lowbit 操作+前缀和 / 差分思想,所有的进阶用法都是这两个核心的延伸。这 6 道模板题覆盖了树状数组的所有经典用法,是打通树状数组的 “通关宝典”。 刷完这 6 道题,你不仅能掌握树状数组的各类实现,更能理解其背后的设计思想,面对竞赛和笔试中的区间统计问题,能快速选择最优的树状数组解法。建议大家把每道题的代码手写 2-3 遍,直到能独立默写并解释每一行的含义,真正做到吃透树状数组! 如果觉得这篇文章对你有帮助,欢迎点赞、收藏、关注~后续会继续更新树状数组的拓展应用题解析,敬请期待!🚀