#创作计划# 树状数组（2）
2026-08-14 20:16:16
发布于：广东
20阅读
0回复
0点赞
生产队的驴在集训营也要生产。本文完成
前情提要：树状数组（1）
前言
为啥要区间修改和单点查询啊。
线段树真好玩，嘿嘿。
（被 RE 扇飞了）
滚回来写树状数组。
正文
前文回顾
上一文章我们讲解了单点修改和前缀和查询的树状数组。
前置知识 - 差分
差分数组的每一项代表原数组这一项和前一项的差，即：
d[i] = a[i] - a[i - 1];
注意到由于差分数组是原数组两项之间的差，通过对差分数组做前缀和可以得到原数组。
差分数组方便进行区间修改，如果要对 区间加上 ，只需要对 加上 然后对 减去 即可，即：
d[l] += k;
d[r + 1] -= k;
区间修改和单点查询的树状数组
注意到树状数组的核心是前缀和。
如果我们让树状数组维护差分数组，那么由于查询操作是一个前缀和，可以将查询的结果从查询前缀和转为查询下标的当前值。
同时将修改操作改为标准的差分操作即可，注意建树也要进行修改。
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);
}
// 将 [l, r] 加上 val
void modify(int l, int r, int val) {
add(l, val);
add(r + 1, -val);
}
// 查询 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] - a[i - 1]);
}
注意到只有少量修改。
例题
P3368 【模板】树状数组 2 / A22467.【模板】树状数组 2
标准的区间修改单点查询。
#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);
}
// 将 [l, r] 加上 val
void modify(int l, int r, int val) {
add(l, val);
add(r + 1, -val);
}
// 查询 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] - a[i - 1]);
}
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, y, k;
cin >> x >> y >> k;
modify(x, y, k);
}
else{
int x;
cin >> x;
cout << query(x) << endl;
}
}
}
下期预告
也许会有下期？
有帮助，赞一个