题目描述
原始的树状数组操作:单点修改,区间查询
如果令树状数组存储原数组的差分数组的话,那么操作就变为:
1. 区间修改
2. 单点查询(对差分数组来说,是一个区间和)
注意修改和查询过程中,都要使用线段树的add和ask方法,不能直接累加或者直接+-
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=100010;
int a[N],tr[N],b[N];
int n;
int lowbit(int x)
{
return x&-x;
}
void add(int x,int c)
{
for(int i=x;i<=n;i+=lowbit(i))
tr[i] += c;
}
ll sum(int x)
{
ll res=0;
for(int i=x;i;i-=lowbit(i))
res+=tr[i];
return res;
}
int main()
{
int m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
//直接将差分数组保存至线段树
for(int i=1;i<=n;i++)
{
add(i,a[i]-a[i-1]);
}
while(m--)
{
char op;
cin>>op;
if(op=='C')
{
int l,r,d;
cin>>l>>r>>d;
add(l,d);
add(r+1,-d);
//tr[l]+=d;
//tr[r+1]-=d;
}
else
{
int x;
cin>>x;
int res= sum(x);
cout<<res<<endl;
}
}
return 0;
}