include

include

include

include

using namespace std;int n,m,a[11000],c[11000];//差分建树，区间更新int lowbit(int x){return x}void updata(int i,int k)//单点更新{while(i<=n){c[i]+=k;i+=lowbit(i);}}int getsum(int i)//单点查询{int sum=0;while(i>0){sum+=c[i];i-=lowbit(i);}return sum;}//区间查询

int main(){cin>>n;for (i=1;i<=n;i++){cin>>a[i];updata(i,a[i]-a[i-1]);//输入初值的时候，也相当于更新了值}//区间更新(还是单点...)//[x,y]区间内加上kupdata(x,k);updata(y+1,-k);

return 0;

}

---

include

include

include

using namespace std;int n,m,a[11000],sum1[11000],sum2[11000];int lowbit(int x){return x}void updata(int i,int k){int x=i;while(i<=n){sum1[i]+=k;sum2[i]+=k(x-1);i+=lowbit(i);}}int getsum(int i)//求前缀和{int res=0,x=i;while (i>0){res+=xsum1[i]-sum2[i];i-=lowbit(i);}return res;}int main(){int i,j;cin>>n;for (i=1;i<=n;i++){cin>>a[i];updata(i,a[i]-a[i-1]);//差分}//[x,y]区间内加上kupdata(x,k);updata(y+1,-k);

int sum=getsum(y)-getsum(x-1);//求区间和 return 0;

}

自用模板，树状数组