线段树：线段树用来储存区域信息

主要有五种操作：

建树、单点查询、单点修改、区间查询、区间修改。

注意和树状数组一样不能处理位置0

#include
      
       using namespace std;//input by bxd#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define repp(i,a,b) for(int i=(a);i>=(b);--i)#define RI(n) scanf("%d",&(n))#define RII(n,m) scanf("%d%d",&n,&m)#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)#define RS(s) scanf("%s",s);#define ll long long#define pb push_back#define REP(i,N)  for(int i=0;i<(N);i++)#define CLR(A,v)  memset(A,v,sizeof A)//#define inf 0x3f3f3f3f#define lson l,m,pos<<1#define rson m+1,r,pos<<1|1const int N=100000+2;ll sum[N<<2],col[N<<2];void up(int pos){    sum[pos]=sum[pos<<1]+sum[pos<<1|1];}void down(int pos,int m){    if(col[pos])    {        col[pos<<1]+=col[pos];        col[pos<<1|1]+=col[pos];        sum[pos<<1]+=col[pos]*(m-(m>>1));        sum[pos<<1|1]+=col[pos]*(m>>1);        col[pos]=0;    }}void build(int l,int r,int pos){    col[pos]=0;    if(l==r)    {        scanf("%lld",&sum[pos]);        return ;    }    int m=(l+r)>>1;    build(lson);    build(rson);    up(pos);}void update(int L,int R,int v,int l,int r,int pos){    if(L<=l&&r<=R)    {        sum[pos]+=(r-l+1)*v;        col[pos]+=v;        return ;    }    down(pos,r-l+1);    int m=(l+r)>>1;    if(L<=m)update(L,R,v,lson);    if(R>m)update(L,R,v,rson);    up(pos);}ll query(int L,int R,int l,int r,int pos){    if(L<=l&&r<=R)    {        return sum[pos];    }    down(pos,r-l+1);    ll ans=0;    int m=(l+r)>>1;    if(L<=m)ans+=query(L,R,lson);    if(R>m)ans+=query(L,R,rson);    return ans;}