线段树代码,零分求调。
#include<bits/stdc++.h>
using namespace std;
int n,m,num[(int)1e5],tree[(int)4e5];
int op,x,y,k;
void pushup(const int x)//更新
{
tree[x] = tree[x*2]+tree[x*2+1];
}
void build(const int x,int l,int r)//建树
{
if(l == r)tree[x] = num[l];
else
{
int mid = (l+r)/2;
build(x*2,l,mid);build(x*2+1,mid+1,r);
pushup(x);
}
}
int point_que(int now,int l,int r,const int x)//单点查询
{
if(l == r)return tree[now];
else
{
int mid = (l+r)/2;
if(x >= mid)return point_que(now*2+1,mid+1,r,x);
else return point_que(now*2,l,mid,x);
}
}
void point_update(int now,int l,int r,const int x,const int chn)//单点修改
{
if(l == r)tree[now]+=chn;
else
{
int mid = (l+r)/2;
if(x >= mid)point_update(now*2+1,mid+1,r,x,chn);
else point_update(now*2,l,mid,x,chn);
pushup(now);
}
}
int ask(int now,const int L,const int R,int l,int r)//区间查询
{
if(L <= l && R >= r)return tree[now];//[l,r]被[L,R]包含
else
{
if(!((l > R) || (r < L)))//有交
{
int mid = (l+r)/2;
return ask(now*2,L,R,l,mid)+ask(now*2+1,L,R,mid+1,r);
}
else return 0;
}
}
int main()
{
cin >>n>>m;
for(int i = 1; i <= n; i++)cin >>num[i];
build((1+n)/2,1,n);
while(m--)
{
cin >>op>>x>>y;
if(op == 1)
{
cin >>k;
for(int i = x; i <= y; i++)point_update((1+n)/2,1,n,i,k);
}
if(op == 2)
{
cout <<ask((1+n)/2,x,y,1,n)<<"\n";
}
}
}