数据结构——树状数组（Binary Indexed Tree）

数据结构——树状数组（Binary Indexed Tree）

TS12 will see u on Oct.03

树状数组是一种可以快速区间修改和元素查询的结构，是线段树的低配版。原理是利用lowbit分解，大致感觉和二进制分解比较像，时间同样是$log$级别的 。其实英文和它的作用更加贴切，就是通过二进制的索引产生像树一样的结构。

算法解释

树状数组的本质是用一个 “压缩版” 的树结构来存储数组的前缀和，核心是**lowbit **

关于lowbit

lowbit (x) 的定义：返回 x 的二进制表示中，最低位的 1 所对应的值。

比如：

• x=5（二进制 101），最低位 1 在第 0 位（从 0 开始计数），对应值为 1，故 lowbit (5)=1；
• x=6（二进制 110），最低位 1 在第 1 位，对应值为 2，故 lowbit (6)=2；
• x=8（二进制 1000），最低位 1 在第 3 位，对应值为 8，故 lowbit (8)=8。

计算方式：由于计算机用补码存储负数，x & -x 即可直接得到 lowbit (x)（原理：-x 的补码是 x 取反 + 1，与 x 相与后仅保留最低位 1）。

代码：

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

接下来对照着树状数组的结构来说一下大概的操作流程。

为了方便解释，我们把最原始的数据当做a数组，上边的"前缀和数组叫做“c数组”。可以看到，每一个c数组都是有一个管辖范围的，而查询就是通过不断爬这些管辖范围从后往前得到的。下面从一张表格直观的将“管辖范围”表示出来：

C 数组下标 i	lowbit(i)	管辖区间	区间和
1	1	[1,1]	a[1]
2	2	[1,2]	a[1]+a[2]
3	1	[3,3]	a[3]
4	4	[1,4]	a[1]+a[2]+a[3]+a[4]
5	1	[5,5]	a[5]
6	2	[5,6]	a[5]+a[6]
7	1	[7,7]	a[7]
8	8	[1,8]	a[1]+a[2]+…+a[8]

单点添加，区间查询

P3374 【模板】树状数组 1 - 洛谷

如果说我们此时要求a[7]的前缀和，那么过程就是这样的： query[7]=c[7]+c[6]+c[4]。此时会发现通过lowbit从后往前爬刚好完全覆盖整个区间。

单点添加

如果我们要对某一个点进行添加，那么它会影响到它后边的元素。为什么呢？我们这样想：如果要求一个元素的前缀和，要对前面的所有可能的c数组进行相加。如果我对此时的点进行添加，那么对所有要用到此c数组的元素都进行相加。

具体代码

void add(int x, int y)//单点增加，只影响它自己和它后面的
{for(int i=x; i<=n; i+=lowbit(i))c[i]+=y;
}

区间查询

如果说我们此时要求某一段区间[L,R]之和的时候就可以先求query®再求query(L-1)，最后query®-query(L-1)就是最终答案了。

具体代码

int query(int x)//查询，都是向前查找
{int ans=0;for(int i=x; i>0; i-=lowbit(i))ans+=c[i];return ans;
}

---

代码

// Problem: 洛谷P3374【模板】树状数组 1
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3374
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Submission Time: 2025-08-21 17:34:39#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fi first
#define se second 
#define endl '\n'
const int INF = 1e18;
const int N = 1e6+5;
int c[N];
int n,m;
string s;
int lowbit(int x)
{return x&-x;
}
void add(int x, int y)//单点增加，只影响它自己和它后面的
{for(int i=x; i<=n; i+=lowbit(i))c[i]+=y;
}
int query(int x)//查询，都是向前查找
{int ans=0;for(int i=x; i>0; i-=lowbit(i))ans+=c[i];return ans;
}
void solve()
{cin >> n >> m;//数列的数字个数，操作个数for(int i=1; i<=n; i++)//此时的c[i]相当于是一个前缀和数组{int x;cin >> x;add(i,x);//输入的时候直接按照树状数组的结构，相当于单点添加了}int op;while(m--){int x,y;cin >> op >> x >> y;if(op==1) add(x,y);else cout << query(y)-query(x-1) << endl;}
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T=1;// cin >> T;while(T--) solve();return 0;
}

区间修改，单点查询

差分转换

设计到区间修改的问题我们很快就能想到前缀和或者是差分。由于原来的c数组是一种类似于前缀和的数组，我们想要直接得到原始的值就需要进行差分。这样的话利用树状数组的特殊结构就能很快得到目标区间的和。主要是涉及到了差分的操作，其他还和原来是一样的。

代码

// Problem: 洛谷P3368【模板】树状数组 2
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3368
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Submission Time: 2025-08-22 19:09:06#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fi first
#define se second 
#define endl '\n'
const int INF = 1e18;
const int N = 5e5+5;
int a[N],c[N];
int n,m;
string s;
int lowbit(int x)
{return x&(-x);
}
void add(int x, int y)
{for(int i=x; i<=n; i+=lowbit(i))c[i]+=y;
}int query(int x)
{int ans=0;for(int i=x; i>0; i-=lowbit(i))ans+=c[i];return ans;
}void solve()
{cin >> n >> m;for(int i=1; i<=n; i++) cin >> a[i];add(1,a[1]);//add操作会让它后边的全部加上这个数for(int i=2; i<=n; i++)//原来的c[i]相当于前缀和数组，经过差分之后变为正常数组了{int d=a[i]-a[i-1];add(i,d);}while(m--){int op;cin >> op;if(op==1){int l,r,k;cin >> l >> r >> k;add(l,k);if(r+1<=n) add(r+1,-k);}else{int x;cin >> x;cout << query(x) << endl;}}
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T=1;// cin >> T;while(T--) solve();return 0;
}