【数据结构】线段树

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构．

线段树可以在$O(\log n)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作．

P3372 【模板】线段树 1

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

• 将某区间每一个数加上 𝑘．
• 求出某区间每一个数的和．

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int MAXN=1e5;
int n,m;
int a[MAXN];
int val[(MAXN<<2)+10],tag[(MAXN<<2)+10],len[(MAXN<<2)+10];
int ls(int u){return u<<1;}
int rs(int u){return u<<1|1;}
void add_tag(int u,int v)
{
    val[u]+=len[u]*v;
    tag[u]+=v;
}
void pushup(int id)
{
    val[id]=val[ls(id)]+val[rs(id)];
}
void pushdown(int u)
{
    if(!tag[u])return ;
    add_tag(ls(u),tag[u]);
    add_tag(rs(u),tag[u]);
    tag[u]=0;
}
int read()
{
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
void build(int u,int l,int r)
{
    len[u]=r-l+1;
    if(l==r){val[u]=a[l];return;}
    int mid=l+((r-l)>>1);
    build(ls(u),l,mid),build(rs(u),mid+1,r);
    pushup(u);
}
void modify(int u,int ql,int qr,int l,int r,int v)
{
    //与修改区间完全错开，直接返回
    if(qr<l||r<ql)return ;
    //被修改区间包含，在当前节点直接打tag
    //等到有询问时再修改子节点
    if(ql<=l&&r<=qr){add_tag(u,v);return ;}
    //当前区间包含修改区间
    int mid=l+((r-l)>>1);
    pushdown(u);
    modify(ls(u),ql,qr,l,mid,v),modify(rs(u),ql,qr,mid+1,r,v);
    pushup(u);
}
int query(int u,int ql,int qr,int l,int r)
{
    //与修改区间完全错开，直接返回
    if(qr<l||r<ql)return 0;
    //被修改区间包含，在当前节点直接打tag
    //等到有询问时再修改子节点
    if(ql<=l&&r<=qr)return val[u];
    //当前区间包含修改区间
    int mid=l+((r-l)>>1);
    pushdown(u);
    return query(ls(u),ql,qr,l,mid)+query(rs(u),ql,qr,mid+1,r);
}   
signed main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    build(1,1,n);
    while(m--)
    {
        int opt=read();
        if(opt==1)
        {
            int l=read(),r=read(),v=read();
            modify(1,l,r,1,n,v);
        }
        else
        {
            int l=read(),r=read();
            cout<<query(1,l,r,1,n);
            puts("");
        }
    }
}