P3368 【模板】树状数组 2 题解
Drink_Assam
·
·
题解
树状数组是单点修改、区间查询，而这题是区间修改、单点查询，相当于动态的差分，维护差分数组就可以单点修改、区间查询。
设这个序列是 a，它的长度是 n，它的差分数组是 d，即对于所有整数 j\in[2,n] 都有 d_j=a_j-a_{j-1}，特别地 d_1=a_1，显然 a_x=\sum\limits_{i=1}^x d_i。
当执行操作 1，区间 [x,y] 内每个数都加上 k 的时候，d_x 加上 k，d_{y+1} 减去 k（当 y=n 时不减）。
当执行操作 2，要输出 a_x 的值时，输出 \sum\limits_{i=1}^n d_i 就好了。
代码如下。
```cpp
#include <iostream>
#define int long long
using namespace std;
int n,q,c[1000001];
void upd(int i,const int x) {
for(;i<=n;i+=i&-i) c[i]+=x;
}
int query(int i) {
int ret=0;
for(;i;i-=i&-i) ret+=c[i];
return ret;
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false),
cout.tie(nullptr);
cin>>n>>q;
for(int a,i=1;i<=n;i++) {
cin>>a;
upd(i,a);
upd(i+1,-a);
}
for(int op,l,r,x;q--;) {
cin>>op;
if(op==1) {
cin>>l>>r>>x;
upd(l,x);
upd(r+1,-x);
} else {
cin>>x;
cout<<query(x)<<'\n';
}
}
return 0;
}
```