蒟蒻刚学完树状数组,用区间查询+区间修改的方法TIE了后面两个点,想问一下这题是不是只能用区间修改+单点查询的方法。 附上代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long sum1[503030];
long long sum2[504024];
int a[503030];
int N,M;
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int k)
{
int xx=x;
while(x<=N)
{
sum1[x]+=k;
sum2[x]+=(xx-1)*k;
x+=lowbit(x);
}
}
long long search(int x)
{
long long s=0;
int i=x;
while(x>0)
{
s+=i*sum1[x]-sum2[x];
x-=lowbit(x);
}
return s;
}
long long ask(int l,int r)
{
return search(r)-search(l-1);
}
int main()
{
cin>>N>>M;
for(int i=1;i<=N;i++)
{
cin>>a[i];
add(i,a[i]-a[i-1]);
}
for(int i=1;i<=M;i++)
{
int z,l,r,k;
int x;
cin>>z;
if(z==1)
{
cin>>l>>r>>k;
add(l,k);
add(r+1,-k);
}
if(z==2)
{
cin>>x;
cout<<ask(x,x)<<endl;
}
}
return 0;
}