今天突然想用树状数组来打线段树板子,然后第一次查询时没有令 l−1 但是A了。 后来发现这个问题,改完以后还是A了,但是 l 肯定会对答案造成影响,疑惑。 代码
#include<bits/stdc++.h>
#define int long long
#define N (int)1e5+10
#define fo(n) for(int i=1;i<=n;i++)
using namespace std;
int a[N],n,m,c1[N],c2[N];
inline int read(){
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+48);
}
inline void add(int x,int k){
int l=x;
for(;x<=n;x+=x&-x)c1[x]+=k,c2[x]+=l*k;
}
inline void query(int l,int r){
int ans1=0,ans2=0;
for(int i=r;i;i-=i&-i)ans1+=c1[i],ans2+=c2[i];
int sum=ans1*(r+1);ans1=0;
for(int i=l;i;i-=i&-i)ans1+=c1[i],ans2-=c2[i];
write(sum-l*ans1-ans2);putchar('\n');
}
main(){
n=read(),m=read();
fo(n)a[i]=read(),add(i,a[i]),add(i+1,-a[i]);
fo(m){
int pd=read();
int a=read(),b=read();
if(pd==1){int k=read();add(a,k),add(b+1,-k);}
else query(a,b);
}
return 0;
}
这里的 l 并没有减1
for(int i=l;i;i-=i&-i)ans1+=c1[i],ans2-=c2[i];
求教