暴力树状数组30分,这该怎么办;
知识点回顾
差分数组中
开头结尾改变了值之后
求他的前缀,发现区间内所有数都改变
然后我们做差分树状数组
#include<cstdio>
using namespace std;
int n,m;
int c[];
int lowbit(int x){
return x&-x;
}
void update(int i,int x){
while(i <= n){
c[i] += x;
i += lowbit(i);
}
}
int sum(int x)
{
int sum = ;
while(x){
sum += c[x];
x -= lowbit(x);
}
return sum;
}
int main()
{
scanf("%d%d",& n,& m);
int x, y, z, k;
for(int i = ;i <= n;++ i){
scanf("%d",& x);
update(i,x),update(i+,-x);
}
while(m-- ){
scanf("%d",& z);
if(z == ){
scanf("%d",& x);
printf("%d\n",sum(x));
}else{
scanf("%d%d%d",& x,& y,& k);
update(x, k);update(y+, -k);
}
}
return ;
}