前言在算法学习中处理单点修改和区间查询问题时你是否还在为线段树的冗长代码头疼是否想找一个效率相当、实现更简洁的数据结构今天要介绍的树状数组Binary Indexed Tree简称 BIT就是你的最优解树状数组是一种专为区间统计设计的高效数据结构修改和查询的时间复杂度均为O(logN)代码量只有线段树的 1/3时间效率常数也更小。它能解决线段树的部分核心问题是算法竞赛、笔试面试中处理区间问题的 “利器”。本文将从原理到实战由浅入深讲解树状数组包括一维、二维的各种操作让你从零开始吃透树状数组下面就让我们正式开始吧一、树状数组的引入1.1 树状数组的定位树状数组是一种仅支持单点修改和区间查询的线性数据结构核心解决的是序列的区间统计问题如区间和、区间乘积其所有操作的时间复杂度均为O(logN)在数据量达到106甚至107时仍能高效运行。它和线段树的关系可以用一句话概括树状数组能解决的问题线段树一定能解决但线段树能解决的问题树状数组不一定能解决。树状数组是线段树的 “简化版”舍弃了部分通用性换来了极致的简洁和效率。1.2 树状数组的适用场景树状数组维护的信息需要满足两个核心条件结合律如区间和中(ab)c a(bc)区间乘积中(a*b)*c a*(b*c)可差分可减性能通过前缀信息相减得到任意区间的信息比如区间和可以用[1,r] - [1,l-1]得到[l,r]的和。注意如果信息不满足可差分树状数组就无法维护比如区间最值、区间 GCD这类问题还是需要用线段树解决。1.3 树状数组的学习价值可能有同学会问既然线段树更通用为什么还要学树状数组代码极简树状数组的核心操作修改、查询只有几行循环远少于线段树的结构体 递归 / 非递归实现常数更小树状数组是连续的数组存储没有线段树的节点冗余缓存命中率更高运行速度更快应用广泛算法竞赛中 80% 的区间统计问题都是树状数组能解决的比如逆序对、区间和修改查询、二维子矩阵统计等。二、树状数组维护信息的方式及核心性质为了更好理解树状数组的设计思路我们先从线段树入手看看树状数组是如何对线段树做 “精简” 的。2.1 从线段树到树状数组的精简假设我们有一个长度为 8 的序列用线段树维护区间和时节点结构是这样的线段树的每个节点都维护一个区间和但实际上很多区间的信息可以通过前缀和相减推导出来比如[3,5]的和可以用[1,5]-[1,2]得到这些冗余的节点完全可以舍弃。可以看到树状数组仅保留了线段树中必要的节点用一个普通数组就能存储这就是树状数组的核心设计思路。补充树状数组的原始设计并非来自线段树精简而是通过二进制拆分区间实现的 —— 将任意区间[1,x]拆分成若干个无交集的区间每个区间的长度为lowbit(x)。两种思路殊途同归线段树精简的方式更易理解二进制拆分则是树状数组的本质。2.2 树状数组的核心性质下标从 1 开始树状数组的下标必须从 1 开始这是由 lowbit 操作的特性决定的x0 时 lowbit (0) 无意义其所有操作都围绕lowbit展开核心有 3 个性质这是理解和实现树状数组的关键先定义lowbit(x) x -x作用是保留 x 的二进制中最右边的 1比如x6110lowbit(6)210x81000lowbit(8)81000。性质 1向上爬公式找父节点节点编号为 x 时父节点编号为x lowbit(x)。树状数组是一棵 “不完全的树”每个节点都有对应的父节点修改操作时需要沿着父节点一路向上更新因为父节点维护的区间包含当前节点。性质 2向前跳公式找前一个相邻区间节点编号为 x 时前一个相邻区间的编号为x - lowbit(x)。查询前缀和[1,x]时需要通过这个公式不断向前跳累加每个区间的和直到跳至 0 为止。性质 3节点维护的区间范围节点编号为 x 时该节点维护的区间是[x - lowbit(x) 1, x]。这是树状数组的核心每个节点都有明确的区间管辖范围比如x5101lowbit (5)1维护区间[5,5]x6110lowbit (6)2维护区间[5,6]x81000lowbit (8)8维护区间[1,8]。2.3 树状数组的结构示例n8结合上述性质我们给出 n8 时树状数组的完整节点分布每个节点的编号、lowbit 值、维护区间一目了然节点 x1(001)2(010)3(011)4(100)5(101)6(110)7(111)8(1000)lowbit(x)12141218维护区间[1,1][1,2][3,3][1,4][5,5][5,6][7,7][1,8]通过这个表格你可以清晰看到树状数组的每个节点都只维护一段连续的区间且区间长度恰好是lowbit(x)。三、一维树状数组核心操作与实战一维树状数组是树状数组的基础也是最常用的形式核心解决序列的单点修改 区间查询、区间修改 单点查询、区间修改 区间查询三类问题下面逐一讲解每个问题都给出原理和完整 C 代码。3.1 基础版单点修改 区间查询这是树状数组的最基础用法解决的问题是给定一个长度为 n 的序列执行 m 次操作要么修改某个位置的数值要么查询某个区间[l,r]的和。核心思路单点修改当位置 x 的数值增加 k 时所有包含 x 的树状数组节点都需要更新沿着父节点x lowbit(x)一路向上直到超过 n区间查询利用前缀和思想先查询[1,r]的和再查询[1,l-1]的和两者的差就是[l,r]的和树状数组的创建初始时树状数组全为 0读入序列的每个元素a[i]相当于对位置 i 执行单点修改加 a [i]。核心代码实现#include iostream using namespace std; // 定义lowbit操作宏定义更高效 #define lowbit(x) (x -x) // 数据范围根据题目调整一般开1e510或1e610 typedef long long LL; // 防止溢出区间和建议用long long const int N 1e6 10; int n, m; 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 res 0; for (int i x; i 0; i - lowbit(i)) { res tree[i]; } return res; } // 区间查询查询[l,r]的和 LL interval_query(int l, int r) { return query(r) - query(l - 1); } int main() { ios::sync_with_stdio(false); cin.tie(0); // 加速cin处理大数据必备 cin n m; // 初始化树状数组读入原序列逐个单点修改 for (int i 1; i n; i) { LL x; cin x; modify(i, x); } // 处理m次操作 while (m--) { int op; cin op; if (op 1) { // 操作1单点修改位置x加k int x; LL k; cin x k; modify(x, k); } else { // 操作2区间查询查询[l,r]的和 int l, r; cin l r; cout interval_query(l, r) endl; } } return 0; }代码说明为什么用long long当 n 达到106每个元素为106时区间和会达到1012超出 int 的范围2×109因此必须用 long long 防止溢出输入加速ios::sync_with_stdio(false); cin.tie(0);是 C 处理大数据的常用技巧避免 cin 因同步 stdio 导致的速度变慢操作封装将区间查询封装为interval_query代码更易读。3.2 进阶版 1区间修改 单点查询如果问题变成将区间[x,y]的所有数加 d查询某个位置 i 的数值直接用基础版树状数组无法实现此时需要结合差分思想。核心思路回顾差分的性质对原数组 a 的区间[x,y]加 d等价于对差分数组 diff 的x 位置加 dy1 位置减 d原数组的某个位置 i 的数值等价于差分数组 diff 的前缀和[1,i]。因此区间修改 单点查询的问题可以转化为用树状数组维护差分数组 diff将原问题的区间修改变为树状数组的两次单点修改原问题的单点查询变为树状数组的前缀和查询。核心代码实现#include iostream using namespace std; #define lowbit(x) (x -x) typedef long long LL; const int N 1e6 10; int n, m; LL tree[N]; // 树状数组维护差分数组diff void modify(int x, LL k) { for (int i x; i n; i lowbit(i)) { tree[i] k; } } LL query(int x) { // 查询差分数组的前缀和[1,x]即原数组a[x]的值 LL res 0; for (int i x; i 0; i - lowbit(i)) { res tree[i]; } return res; } // 区间修改原数组[a,b]的所有数加k void interval_modify(int a, int b, LL k) { modify(a, k); if (b 1 n) { modify(b 1, -k); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; // 初始化原数组a[i]转化为差分数组的单点修改 for (int i 1; i n; i) { LL x; cin x; interval_modify(i, i, x); // 对[i,i]加x等价于diff[i]x } while (m--) { int op; cin op; if (op 1) { // 操作1区间修改[l,r]加k int l, r; LL k; cin l r k; interval_modify(l, r, k); } else { // 操作2单点查询查询a[x]的值 int x; cin x; cout query(x) endl; } } return 0; }代码说明初始化技巧原数组的每个元素a[i]可以看作是对差分数组执行interval_modify(i,i,a[i])即对区间[i,i]加 a [i]边界判断执行modify(b1,-k)时需要判断b1 n避免下标越界。3.3 进阶版 2区间修改 区间查询这是一维树状数组的最高阶用法解决的问题是将区间[x,y]的所有数加 k查询区间[l,r]的和。该问题需要结合差分 数学推导用两个树状数组维护不同的信息。核心推导设原数组为 a差分数组为 d满足a[i]∑j1i​d[j]。我们需要求原数组的前缀和S[i] a[1]a[2]...a[i]将 a [j] 用差分数组表示并展开令sum1[i] \sum_{k1}^i d[k]d 数组的前缀和sum2[i] \sum_{k1}^i d[k]×(k-1)d [k]×(k-1) 的前缀和则原数组的前缀和S[i]i×sum1[i]−sum2[i]。原数组的区间和[l,r] S[r] - S[l-1]因此只需用两个树状数组分别维护d[k]和d[k]×(k-1)即可实现区间修改 区间查询。核心思路用树状数组 A 维护d[k]树状数组 B 维护d[k]×(k-1)对原数组区间[x,y]加 k等价于对差分数组 d 执行d[x]k、d[y1]-k因此对 A 和 B 分别执行两次单点修改A.modify(x, k)、A.modify(y1, -k)B.modify(x, k×(x-1))、B.modify(y1, -k×y)求原数组前缀和 S [i]i * A.query(i) - B.query(i)求原数组区间和[l,r]S[r] - S[l-1]。核心代码实现为了让代码更易读我们将树状数组封装为结构体#include iostream using namespace std; #define lowbit(x) (x -x) typedef long long LL; const int N 1e6 10; int n, m; // 封装树状数组结构体复用代码 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 res 0; for (int i x; i 0; i - lowbit(i)) { res tree[i]; } return res; } }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 m; // 初始化原数组a[i] for (int i 1; i n; i) { LL x; cin x; interval_modify(i, i, x); // 对[i,i]加x初始化差分数组 } while (m--) { int op; cin op; if (op 1) { // 操作1区间修改[l,r]加k int l, r; LL k; cin l r k; interval_modify(l, r, k); } else { // 操作2区间查询[l,r]的和 int l, r; cin l r; cout interval_query(l, r) endl; } } return 0; }代码说明结构体封装将树状数组的 modify 和 query 封装为结构体避免重复代码A 和 B 两个树状数组直接复用数据类型所有乘法操作都要强制转换为 long long防止 int 溢出初始化同样用interval_modify(i,i,x)初始化原数组等价于差分数组的单点修改。四、二维树状数组从一维到二维的拓展实际问题中我们不仅需要处理一维序列的统计还会遇到二维矩阵的统计问题比如修改矩阵中某个位置的数值、查询子矩阵的和、对某个子矩阵的所有数加 d 等。此时可以将一维树状数组拓展为二维树状数组核心思想是二维循环分别对行和列执行 lowbit 操作。二维树状数组的下标同样从 (1,1) 开始核心操作是单点修改 区间查询、区间修改 单点查询、区间修改 区间查询拓展方式和一维一致下面逐一讲解。4.1 基础版单点修改 子矩阵查询解决的问题给定 n×m 的二维矩阵执行若干操作要么修改矩阵中位置(x,y)的数值要么查询左上角为(x1,y1)、右下角为(x2,y2)的子矩阵的和。核心思路单点修改对位置(x,y)加 k需要对行和列分别执行向上爬操作即行i lowbit(i)列j lowbit(j)直到超过 n 和 m前缀和查询查询从(1,1)到(x,y)的前缀子矩阵和行i - lowbit(i)列j - lowbit(j)累加所有节点的和子矩阵查询利用二维前缀和思想子矩阵(x1,y1)-(x2,y2)的和为sum(x2,y2)−sum(x1−1,y2)−sum(x2,y1−1)sum(x1−1,y1−1)其中sum(x,y)表示(1,1)到(x,y)的前缀和。核心代码实现#include iostream using namespace std; #define lowbit(x) (x -x) typedef long long LL; // 二维数组的大小根据题目调整比如4200、2060等 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 res 0; for (int i x; i 0; i - lowbit(i)) { for (int j y; j 0; j - lowbit(j)) { res tree[i][j]; } } return res; } // 子矩阵查询(x1,y1)到(x2,y2)的和 LL matrix_query(int x1, int y1, int x2, int y2) { return query(x2, y2) - query(x1-1, y2) - query(x2, y1-1) query(x1-1, y1-1); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; // 初始化二维矩阵 for (int i 1; i n; i) { for (int j 1; j m; j) { LL x; cin x; modify(i, j, x); } } // 处理操作直到文件结束 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子矩阵查询 int x1, y1, x2, y2; cin x1 y1 x2 y2; cout matrix_query(x1, y1, x2, y2) endl; } } return 0; }4.2 进阶版 1区间修改 单点查询解决的问题对 n×m 矩阵的子矩阵(x1,y1)-(x2,y2)的所有数加 d查询矩阵中某个位置(x,y)的数值。同样需要结合二维差分思想。二维差分的核心性质对原矩阵 a 的子矩阵(x1,y1)-(x2,y2)加 d等价于对二维差分数组 diff 执行四次单点修改原矩阵的位置(x,y)的数值等价于二维差分数组 diff 的前缀和sum(1,1,x,y)。因此问题转化为用二维树状数组维护二维差分数组 diff原问题的区间修改变为树状数组的四次单点修改原问题的单点查询变为树状数组的前缀和查询。核心代码实现#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]; // 二维树状数组维护二维差分数组 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) { // 查询diff的前缀和即原矩阵a[x][y]的值 LL res 0; for (int i x; i 0; i - lowbit(i)) { for (int j y; j 0; j - lowbit(j)) { res tree[i][j]; } } return res; } // 区间修改子矩阵(x1,y1)-(x2,y2)加k void matrix_modify(int x1, int y1, int x2, int y2, LL k) { modify(x1, y1, k); if (y2 1 m) modify(x1, y2 1, -k); if (x2 1 n) modify(x2 1, y1, -k); if (x2 1 n y2 1 m) modify(x2 1, y2 1, k); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; // 初始化原矩阵 for (int i 1; i n; i) { for (int j 1; j m; j) { LL x; cin x; matrix_modify(i, j, i, j, x); // 单点初始化 } } int op; while (cin op) { if (op 1) { // 操作1子矩阵加k int x1, y1, x2, y2; LL k; cin x1 y1 x2 y2 k; matrix_modify(x1, y1, x2, y2, k); } else { // 操作2单点查询 int x, y; cin x y; cout query(x, y) endl; } } return 0; }4.3 进阶版 2区间修改 子矩阵查询这是二维树状数组的最高阶用法解决的问题是对矩阵的子矩阵(x1,y1)-(x2,y2)加 k查询另一个子矩阵(a1,b1)-(a2,b2)的和。该问题需要结合二维差分 数学推导用四个二维树状数组维护不同的信息。核心推导设二维原矩阵为 a二维差分数组为 d满足。我们需要求原矩阵的前缀和S[i][j] \sum_{x1}^i \sum_{y1}^j a[x][y]将 a [x][y] 用差分数组表示并展开最终推导可得其中所有求和的范围都是x1到iy1到j。因此我们需要用四个二维树状数组分别维护d[x][y]d[x][y]×xd[x][y]×yd[x][y]×x×y核心代码实现同样封装结构体复用代码代码结构清晰#include iostream using namespace std; #define lowbit(x) (x -x) typedef long long LL; 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 res 0; for (int i x; i 0; i - lowbit(i)) { for (int j y; j 0; j - lowbit(j)) { res tree[i][j]; } } return res; } }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); } // 子矩阵(x1,y1)-(x2,y2)加k void matrix_modify(int x1, int y1, int x2, int y2, LL k) { add(x1, y1, k); add(x1, y2 1, -k); add(x2 1, y1, -k); add(x2 1, y2 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; } // 求原矩阵子矩阵(a1,b1)-(a2,b2)的和 LL matrix_query(int a1, int b1, int a2, int b2) { return prefix_sum(a2, b2) - prefix_sum(a1-1, b2) - prefix_sum(a2, b1-1) prefix_sum(a1-1, b1-1); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; // 处理操作直到文件结束 int op; while (cin op) { if (op 1) { // 操作1子矩阵加k int x1, y1, x2, y2; LL k; cin x1 y1 x2 y2 k; matrix_modify(x1, y1, x2, y2, k); } else { // 操作2子矩阵查询 int a1, b1, a2, b2; cin a1 b1 a2 b2; cout matrix_query(a1, b1, a2, b2) endl; } } return 0; }五、树状数组的核心总结5.1 一维树状数组操作表问题类型核心思路树状数组数量单点修改 区间查询直接维护原数组前缀和1区间修改 单点查询维护差分数组转化为单点操作1区间修改 区间查询差分 数学推导维护两个信息25.2 二维树状数组操作表问题类型核心思路树状数组数量单点修改 子矩阵查询直接维护二维前缀和1区间修改 单点查询维护二维差分数组1区间修改 子矩阵查询二维差分 数学推导维护四个信息45.3 关键注意事项下标从 1 开始这是树状数组的硬性要求x0 时 lowbit (0) 无意义防止溢出所有区间和 / 矩阵和的操作都要用long long避免 int 溢出lowbit 操作核心是x -x仅在 C 中有效负数以补码存储差分的边界执行y1或x21的修改时必须判断是否越界大数据加速C 中用ios::sync_with_stdio(false); cin.tie(0);加速输入输出。总结树状数组是算法学习中性价比极高的一个数据结构花少量的时间学习就能解决大部分区间统计问题。其核心是lowbit 操作和前缀和 / 差分思想从一维到二维的拓展只是维度的增加核心逻辑完全一致。学习树状数组的关键是理解其核心性质而不是死记代码。建议大家先手动推导 lowbit 的计算、节点的维护区间再结合简单的例子如 n8模拟修改和查询的过程这样才能真正掌握树状数组的本质。掌握了树状数组后你可以尝试解决这些经典问题逆序对、楼兰图腾、HH 的项链等这些问题都是树状数组的经典应用能帮助你进一步巩固知识点。希望这篇文章能让你彻底吃透树状数组在算法竞赛和笔试中轻松解决区间统计问题如果有疑问欢迎在评论区留言讨论创作不易点个赞再走吧