原创网站源码,网站设计报价是多少钱,国内用python做的网站,wordpress图库前言 树状数组#xff08;BIT#xff09;作为算法竞赛中处理区间统计的利器#xff0c;凭借代码简洁、时间效率高的特点#xff0c;成为了笔试面试和竞赛中的高频考点。而掌握树状数组的核心#xff0c;就是吃透各类经典模板题 —— 从最基础的单点修改 区间查询#xf…前言树状数组BIT作为算法竞赛中处理区间统计的利器凭借代码简洁、时间效率高的特点成为了笔试面试和竞赛中的高频考点。而掌握树状数组的核心就是吃透各类经典模板题 —— 从最基础的单点修改 区间查询到二维的区间修改 区间查询每一道模板题都是对树状数组核心思想的落地实践。本文将围绕 6 道经典的树状数组模板题展开涵盖一维基础、一维进阶、二维基础、二维进阶全类型每道题都包含题目解析、核心思路、完整 C 代码、代码详解从题目到实现一步到位。刷完这 6 道题你能彻底掌握树状数组的各类用法面对同类问题再也不用愁下面就让我们正式开始吧一、模板题 1树状数组 1 - 单点修改区间查询题目链接https://loj.ac/p/130题目信息来源LibreOJ 130难度★★★核心考点一维树状数组最基础用法单点修改 区间和查询题目描述给定数列 a1​,a2​,...,an​依次进行 q 个操作操作分两类1 i x将 ai​ 加上 x2 l r求区间 [l,r] 的所有元素和即 ∑ilr​ai​。输入要求1≤n,q≤106∣ai​∣,∣x∣≤1061≤l≤r≤n。输出要求对于每个第二类操作输出对应的区间和。核心思路这是树状数组的入门必刷题直接考察树状数组的两个核心操作单点修改位置 x 增加 k从 x 开始沿父节点ilowbit(i)向上更新树状数组节点区间查询利用前缀和思想区间 [l,r] 的和 前缀和 [1,r] - 前缀和 [1,l−1]而前缀和通过 i−lowbit(i) 向前跳累加得到。关键注意数据范围达到 106必须用long long存储树状数组和结果防止 int 溢出同时需要加速 C 的输入输出避免超时。完整 C 代码#include iostream using namespace std; // lowbit操作保留二进制最右边的1 #define lowbit(x) (x -x) // 数据范围1e610用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; }代码详解lowbit 宏定义x -x是树状数组的核心利用补码特性快速获取最右侧的 1数据类型LL别名long long树状数组tree和查询结果都用其存储避免大数溢出输入输出加速ios::sync_with_stdio(false); cin.tie(0);关闭 cin 与 stdio 的同步解除 cin 和 cout 的绑定大幅提升输入速度初始化树状数组初始为 0读入原数组的每个元素a[i]等价于对位置i执行单点修改加a[i]操作处理根据操作类型分支单点修改直接调用modify区间查询通过两个前缀和的差得到结果。二、模板题 2树状数组 2 - 区间修改单点查询题目链接https://loj.ac/p/131题目信息来源LibreOJ 131难度★★★核心考点一维树状数组 差分思想区间修改 单点值查询题目描述给定数列 a1​,a2​,...,an​依次进行 q 个操作操作分两类1 l r x将区间[l,r]的所有元素都加上x2 i求ai​的当前值。输入要求1≤n,q≤106∣ai​∣,∣x∣≤1061≤l≤r≤n。输出要求对于每个第二类操作输出对应的元素值。核心思路树状数组本身不直接支持区间修改需要结合一维差分思想做转化这是树状数组的经典进阶用法差分性质对原数组a的区间[l,r]加x等价于对差分数组d执行d[l]xd[r1]−x若r1≤n单点查询转化原数组的单点值a[i]等价于差分数组d的前缀和[1,i]树状数组维护对象用树状数组维护差分数组d则原问题的区间修改转化为树状数组的两次单点修改原问题的单点查询转化为树状数组的前缀和查询。完整 C 代码#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增加代码可读性同时判断r1≤n避免下标越界初始化技巧原数组的每个元素a[i]可以看作是对差分数组执行区间[i,i]加a[i]直接调用interval_modify即可完成初始化单点查询直接调用query(x)得到的差分数组前缀和就是原数组a[x]的当前值。三、模板题 3树状数组 3 - 区间修改区间查询题目链接https://loj.ac/p/132题目信息来源LibreOJ 132难度★★★核心考点一维树状数组 差分 数学推导区间修改 区间和查询树状数组一维最高阶用法题目描述给定数列 a1​,a2​,...,an​依次进行 q 个操作操作分两类1 l r x将区间[l,r]的所有元素都加上x2 l r求区间[l,r]的所有元素和。输入要求1≤n,q≤106∣ai​∣,∣x∣≤1061≤l≤r≤n。输出要求对于每个第二类操作输出对应的区间和。核心思路这是一维树状数组的最高阶模板题需要结合差分 数学公式推导用两个树状数组分别维护不同的信息是竞赛中的高频考点。关键数学推导设原数组为a差分数组为d原数组的前缀和将a[j]用差分数组展开并化简令则原数组前缀和原数组区间和。实现思路定义两个树状数组分别维护d[k]和d[k]×(k−1)原数组区间[l,r]加x转化为差分数组的两次单点修改同步更新两个树状数组先求前缀和S[r]和S[l−1]再做差得到区间[l,r]的和。为了代码复用将树状数组封装为结构体是竞赛中的常用写法。完整 C 代码#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 两个树状数组直接复用避免重复代码差分数组初始化先手动构建差分数组d再分别将d[i]和d[i]∗(i−1)插入两个树状数组区间修改同步更新对 A 和 B 执行两次单点修改其中 B 的修改值需要计算k∗(x−1)和−k∗y严格遵循推导公式前缀和计算强制转换(LL)i避免 int 和 long long 混合运算导致的溢出。四、模板题 4二维树状数组 1 - 单点修改区间查询题目链接https://loj.ac/p/133题目信息来源LibreOJ 133难度★★★核心考点二维树状数组基础用法单点修改 子矩阵和查询题目描述给出一个n×m的零矩阵A完成若干操作操作分两类1 x y k将元素Ax,y​自增k2 a b c d查询左上角为(a,b)、右下角为(c,d)的子矩阵内所有数的和。输入要求输入操作直到文件结束矩阵下标从 1 开始。输出要求对于每个第二类操作输出对应的子矩阵和。核心思路二维树状数组是一维树状数组的二维拓展核心思路是二维循环分别对行和列执行 lowbit 操作本质还是前缀和思想单点修改对位置(x,y)加k行ilowbit(i)列jlowbit(j)双重循环更新树状数组二维前缀和查询查询(1,1)到(x,y)的前缀子矩阵和行i−lowbit(i)列j−lowbit(j)双重循环累加子矩阵和查询利用二维前缀和公式子矩阵(a,b)−(c,d)的和query(c,d)−query(a−1,d)−query(c,b−1)query(a−1,b−1)容斥原理减去多余部分加回重复减去的部分。完整 C 代码#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; }代码详解二维数组大小设为 4200满足 LibreOJ 该题的所有测试用例可根据实际题目调整双重循环所有操作都是行和列的双重循环严格遵循一维树状数组的操作逻辑只是增加了一个维度容斥公式matrix_query严格实现二维前缀和的容斥原理是二维子矩阵查询的核心必须牢记零矩阵初始化题目中矩阵初始为 0树状数组默认初始化为 0无需额外操作。五、模板题 5二维树状数组 2 - 区间修改单点查询题目链接https://loj.ac/p/134题目信息来源LibreOJ 134难度★★★核心考点二维树状数组 二维差分区间修改 单点值查询题目描述给出一个n×m的零矩阵A完成若干操作操作分两类1 a b c d k将左上角为(a,b)、右下角为(c,d)的子矩阵内所有数自增k2 x y查询元素Ax,y​的当前值。输入要求输入操作直到文件结束矩阵下标从 1 开始。输出要求对于每个第二类操作输出对应的元素值。核心思路与一维区间修改 单点查询的思路一致结合二维差分思想将区间修改转化为单点修改是二维树状数组的经典进阶用法。二维差分核心性质对原矩阵A的子矩阵(a,b)−(c,d)加k等价于对二维差分数组diff执行四次单点修改原矩阵的单点值Ax,y​等价于二维差分数组diff的前缀子矩阵和(1,1)−(x,y)。实现思路用二维树状数组维护二维差分数组diff原矩阵的区间修改转化为树状数组的四次单点修改原矩阵的单点查询转化为树状数组的二维前缀和查询。完整 C 代码#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​的当前值零矩阵初始化树状数组默认初始化为 0无需额外操作符合题目中零矩阵的要求。六、模板题 6二维树状数组 3 - 区间修改区间查询题目链接https://loj.ac/p/135题目信息来源LibreOJ 135难度★★★★核心考点二维树状数组 二维差分 数学推导区间修改 子矩阵和查询树状数组二维最高阶用法题目描述给定一个N×M的零矩阵完成若干操作操作分两类1 a b c d x将左上角为(a,b)、右下角为(c,d)的子矩阵全部加上x2 a b c d查询左上角为(a,b)、右下角为(c,d)的子矩阵内所有数的和。输入要求输入操作直到文件结束矩阵下标从 1 开始。输出要求对于每个第二类操作输出对应的子矩阵和。核心思路这是二维树状数组的最高阶模板题难度比一维更高需要结合二维差分 复杂的数学公式推导用四个二维树状数组分别维护不同的信息是竞赛中的难点也是重点。关键数学推导设原矩阵为A二维差分数组为d原矩阵的前缀子矩阵和将A[x][y]用差分数组展开并化简最终得到其中所有求和的范围都是x1到iy1到j。实现思路定义四个二维树状数组分别维护d[x][y]、d[x][y]×x、d[x][y]×y、d[x][y]×x×y原矩阵的子矩阵修改转化为二维差分数组的四次单点修改同步更新四个树状数组先求原矩阵的前缀子矩阵和S[i][j]再利用二维容斥公式求任意子矩阵的和。同样将二维树状数组封装为结构体简化代码。完整 C 代码#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; }代码详解四个树状数组严格对应推导公式中的四个维护项命名 A、B、C、D 便于记忆add 函数封装将四次单点修改的同步更新封装为add避免重复代码减少出错概率前缀和计算严格遵循推导公式所有乘法操作强制转换为long long防止溢出容斥原理子矩阵查询的matrix_query与二维基础版一致复用二维前缀和的容斥公式。七、六大模板题核心总结题型与树状数组数量对应表题号题型维度树状数组数量核心思想1单点修改 区间查询一维1直接维护原数组前缀和2区间修改 单点查询一维1一维差分 维护差分数组3区间修改 区间查询一维2一维差分 数学推导 双数组维护4单点修改 子矩阵查询二维1二维前缀和 双重循环5区间修改 单点查询二维1二维差分 四次单点修改6区间修改 子矩阵查询二维4二维差分 数学推导 四数组维护通用解题技巧溢出处理所有树状数组和结果优先用long long尤其是数据范围≥1e5 的情况避免 int 溢出输入输出加速C 中处理 1e6 级数据时必须加ios::sync_with_stdio(false); cin.tie(0);否则会超时边界判断差分操作中涉及r1、d1的位置必须判断是否≤n/m避免下标越界结构体封装多树状数组场景下封装为结构体可大幅减少重复代码提升可读性公式牢记一维 / 二维区间修改 区间查询的推导公式是核心必须理解并牢记而非死记硬背。学习建议由浅入深先掌握一维基础题 1再学一维差分题 2最后攻克一维高阶题 3二维部分同理手动推导不要直接抄代码手动推导差分和前缀和的公式理解每一步的含义调试测试每道题都结合示例测试用例手动模拟执行观察树状数组的更新和查询过程拓展练习掌握这 6 道模板题后可尝试洛谷的逆序对、楼兰图腾等题将模板应用到实际场景。总结树状数组的模板题看似繁多实则核心思想高度统一 ——lowbit 操作前缀和 / 差分思想所有的进阶用法都是这两个核心的延伸。这 6 道模板题覆盖了树状数组的所有经典用法是打通树状数组的 “通关宝典”。刷完这 6 道题你不仅能掌握树状数组的各类实现更能理解其背后的设计思想面对竞赛和笔试中的区间统计问题能快速选择最优的树状数组解法。建议大家把每道题的代码手写 2-3 遍直到能独立默写并解释每一行的含义真正做到吃透树状数组如果觉得这篇文章对你有帮助欢迎点赞、收藏、关注后续会继续更新树状数组的拓展应用题解析敬请期待