题目大意
维护一个长度为 n 的数组，支持两类操作：
1）对区间 [l,r] 所有元素加上一个值。
2）查询单点 a[x] 的当前值。
P3368 BIT2 区别在于区间加减和单点查询
视频教程
https://www.bilibili.com/video/BV1pE41197Qj?spm_id_from=333.788.recommend_more_video.-1&vd_source=4350e5f2584d2f27c848b347ea11b675
tr实际上是一个差分数组，只不过用了树状数组维护，a[ ]即原始数组就是diff的前缀和，所以甚至不需要再建一个前缀和数组
https://www.luogu.com.cn/record/180209186
和这题代码基本一样，还是比较适合我复训的。
我们来解释一下为什么可以这样pushup
1
2
3
4
5
6
| inline void invert(ll s,ll e){
pushup(s, 1);
if(e<n){
pushup(e+1, -1);
}
}
|
众所周知，我们知道差分数组是给diff[s]+1，给diff[e+1]-1，那为什么可以直接pushup那？那是因为树状数组中遍历你上面的数组是必然遍历不到你的，这点你不用担心，所以不用担心差分连续加导致出错。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <iostream>
typedef long long ll;
using namespace std;
const int maxn=5e5+10;
ll n,m,tr[maxn],a[maxn],x,y,k,op;
inline int lowbit(ll x){
return (x&(-x));
}
inline void add(ll p,ll v){
while(p<n+1){
tr[p]+=v;
p+=lowbit(p);
}
}
ll search(ll p){
if(p==0) return 0;
return search(p-lowbit(p))+tr[p];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
tr[i]=a[i]-a[i-lowbit(i)];
}
for(int _=1;_<=m;_++){
cin>>op;
if(op==1){
cin>>x>>y>>k;
add(x,k);
if(y+1<=n)
add(y+1,-k);
}else{
cin>>x;
int ans=search(x);
cout<<ans<<endl;
}
}
}
|