模板-线段树

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数加上x

2.求出某区间每一个数的和

输入输出格式

输入格式：
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数，表示一个操作，具体如下：

操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式：
输出包含若干行整数，即为所有操作2的结果。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 1000001
#define ll long long
ll a[maxn],f[maxn<<2],tag[maxn<<2];
ll n,m,k,c,x,y;
void push_up(ll x){f[x]=f[x<<1]+f[x<<1|1];}
void push_down(ll p,ll l,ll r){
    ll mid=(l+r)>>1,ls=p<<1,rs=p<<1|1,k=tag[p];
    tag[p]=0;tag[ls]+=k;tag[rs]+=k;
    f[ls]+=(mid-l+1)*k;f[rs]+=(r-mid)*k;
}
void build(ll p,ll l,ll r){
    if(l==r){f[p]=a[l];return;}
    ll mid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    push_up(p);
}
void update(ll l,ll r,ll nl,ll nr,ll p,ll k){
    if(l>=nl&&r<=nr){f[p]+=(r-l+1)*k;tag[p]+=k;return;}
    push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(mid>=nl) update(l,mid,nl,nr,p<<1,k);
    if(mid<nr) update(mid+1,r,nl,nr,p<<1|1,k);
    push_up(p);
}
ll query(ll l,ll r,ll ql,ll qr,ll p){
    if(l>=ql&&r<=qr) return f[p];
    push_down(p,l,r);
    ll ans=0,mid=(l+r)>>1;
    if(mid>=ql) ans+=query(l,mid,ql,qr,p<<1);
    if(mid<qr) ans+=query(mid+1,r,ql,qr,p<<1|1);
    return ans;
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",a+i);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        scanf("%lld",&c);
        if(c==1){scanf("%lld%lld%lld",&x,&y,&k);update(1,n,x,y,1,k);}
         else{scanf("%lld%lld",&x,&y);printf("%lld\n",query(1,n,x,y,1));}
    }
    return 0;
}

模板-线段树

原文：https://www.cnblogs.com/zzx-fovever/p/10654271.html