#创作计划# 树状数组(1)
2026-06-06 15:36:49
发布于：广东
前言
写这玩意的时候我突发奇想写了个线段树交了模板题，然后 了。
这件事情告诉我们 xds 有风险，摇轮椅需谨慎。
本文遵循了洛谷和 ACGO 的格式手册。
正文
什么是树状数组？
树状数组可以实现带修改的区间查询操作。
注意到这个操作可以由线段树实现，但是正如上面所说线段树容易让你受到
Received signal 11: Segmentation fault with invalid memory reference.
的诅咒，所以还是树状数组好使。同时，树状数组的空间占用低于线段树。
讲解树状数组
这段的图片回去会重做的。
首先这个是一个随机（？）序列（最下面是下标）：
1 9 1 9 8 1 0 2
---------------
1 2 3 4 5 6 7 8
我们要对这个序列建树状数组。为此，我们两两合并：
10 10 9 2
1 9 1 9 8 1 0 2
-----------------------------
1 2 3 4 5 6 7 8
20 11
10 10 9 2
1 9 1 9 8 1 0 2
-----------------------------
1 2 3 4 5 6 7 8
31
20 11
10 10 9 2
1 9 1 9 8 1 0 2
-----------------------------
1 2 3 4 5 6 7 8
然后，我们注意到：
- 求下标 的前缀和需要下标 位置上的 ；
- 求下标 的前缀和需要下标 位置上的 ；
- 求下标 的前缀和需要下标 位置上的 ，下标 位置上的 ；
显然只有这些是需要的（最下面保留了一层原数组，用横线表示了管辖范围）：
- - - - - - - 31
- - - 20
- 10 - 9
1 1 8 0
-----------------------------
1 9 1 9 8 1 0 2
-----------------------------
1 2 3 4 5 6 7 8
你稍微观察就可以发现，每一个下标只有一个对应的数字，因此得到数组 ：
1 10 1 20 8 9 0 31
-----------------------------
1 2 3 4 5 6 7 8
这就是树状数组。
然后我们要实现两个操作：前缀和查询和单点修改。
修改
先把上面扒来：
1 10 1 20 8 9 0 31
-----------------------------
1 2 3 4 5 6 7 8
比如说我们要把下标为 的元素增加 。
区间修改的思路如下：
首先我们需要知道，具体要对树状数组的哪些元素进行修改。
看图我们发现，需要修改下标为 , , 的元素。
然后我们发现：
然后继续运用惊人的注意力，得到：
然后我们就可以得到区间修改的思路：
将当前下标 加上修改的数，然后将 加上 。
int n;
ll t[N];//树状数组
//......
// 将 id 位置加上 x
void add(int id, int x){
while(id <= n) t[id]+=x, id += lowbit(id);
}
具体证明详见 OI - Wiki，或者也许哪天我会把证明搬过来？（其实我在 Wiki 也没有找到单独的证明，大概是有依据的）
前缀和查询
还是这个数组。
1 10 1 20 8 9 0 31
-----------------------------
1 2 3 4 5 6 7 8
现在，我们查询下标为 的元素的前缀和。
观察管辖区间：
- - - - - - - 31
- - - 20
- 10 - 9
1 1 8 0
-----------------------------
1 9 1 9 8 1 0 2
-----------------------------
1 2 3 4 5 6 7 8
我们会用到树状数组中下标为 ，， 的元素。
根据上面的经验，我们再次转换为二进制：
然后继续注意。
得到：
将当前答案加上树状数组下标为 的数，然后将 减去 。
// 查询 id 位的前缀和
ll query(int id){
ll res = 0;
while(id > 0) res += t[id], id -= lowbit(id);
return res;
}
建树
首先我们注意到初始的树状数组每一元素都是 ，可以看作对一个全是 的数组建立的树状数组。
然后对于有值的数组建立树状数组，我们可以看作在对所有元素为 建立的树状数组的基础上，对于每一元素加上对应的原数组的值。
// 建立树状数组
void build(){
for(int i = 1; i <= n; i++) add(i, a[i]);
}
完整模板
const int N = 5e5+10;
ll t[N];
int a[N], n, m;
inline int lowbit(int x){ //fun fact: inline 标识其实没用，编译器会自动推断是否内联。
return x & -x;
}
// 将 id 位置加上 x
void add(int id, int x){
while(id <= n) t[id]+=x, id += lowbit(id);
}
// 查询 id 位的前缀和
ll query(int id){
ll res = 0;
while(id > 0) res += t[id], id -= lowbit(id);
return res;
}
// 建立树状数组
void build(){
for(int i = 1; i <= n; i++) add(i, a[i]);
}
例题
P3374 【模板】树状数组 1 / A22721.【模板】树状数组 1
纯模板，我们直接丢一个模板然后浇上浓浓的汁输入输出。
注意到区间的查询和正常前缀和的查询近似。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5+10;
ll t[N];
int a[N], n, m;
inline int lowbit(int x){ //fun fact: inline 标识其实没用，编译器会自动推断是否内联。
return x & -x;
}
// 将 id 位置加上 x
void add(int id, int x){
while(id <= n) t[id]+=x, id += lowbit(id);
}
// 查询 id 位的前缀和
ll query(int id){
ll res = 0;
while(id > 0) res += t[id], id -= lowbit(id);
return res;
}
// 建立树状数组
void build(){
for(int i = 1; i <= n; i++) add(i, a[i]);
}
int main(){
cin >> n >> m;
int x;
for(int i = 1; i <= n; i++) cin >> a[i];
build();
while(m--){
int op;
cin >> op;
if(op == 1){
int x, k;
cin >> x >> k;
add(x, k);
}
else{
int x, y;
cin >> x >> y;
cout << (query(y) - query(x-1)) << endl;
}
}
}
下期预告
树状数组的区间修改和单点查询。
---全文完---
有帮助，赞一个