题解 P3368 【【模板】树状数组 2】
Drug__Lover
2017-10-23 20:24:44
**楼下众神犇好像都用了一个这个东西**
```cpp
change(i,a1[i]-a1[i-1]);
```
**对于蒟蒻的我当时并不理解**
**只好半懵逼半清醒的抄上AC了**
**很久之后的现在又来做了一下这道题**
**发现了一个好理解的?(题解并没有看到底,不知道有没有重复的)**
**对于修改我们可以用树状数组维护差分数组**
**但是用树状数组我们仅维护修改的值(也就是改变的值)**
**最后查询的时候加上初始值就好了**
```cpp
#include<iostream>
#include<cstdio>
#define maxn 500100
using namespace std;
int n,m;
int c[maxn];
int a[maxn];
int add(int x,int k)
{
for(int i=x;i<=n;i+=i&(-i)) c[i]+=k;
}
int query(int x)
{
int sum=0;
for(int i=x;i>0;i-=i&(-i)) sum+=c[i];
return sum;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
while(m--)
{
int k;
scanf("%d",&k);
if(k==1)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,z); //维护查分数组
add(y+1,-z);
}
else
{
int x;
scanf("%d",&x);
printf("%d\n",a[x]+query(x)); //query()求的是改变的值,再加上原来的值就可以了
}
}
return 0;
}
```