線段樹初步

最基本的線段樹：

支援區間加，區間查詢，帶懶标記。

例題：codevs1082 線段樹練習3

題意不再贅述。

代碼：

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=+;
inline int getint()
{
    int x=,f=;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-;c=getchar();}
    while(c>='0'&&c<='9'){x=x*+c-'0';c=getchar();}
    return x*f;
}
int n,q,data[maxn];
struct segment_tree{int l,r,tag;long long sum;}tree[maxn*];

void build(int k,int l,int r)
{
    tree[k].l=l,tree[k].r=r;
    if(l==r){tree[k].sum=data[l];return ;}
    int mid=(l+r)>>;
    build(k<<,l,mid);
    build(k<<|,mid+,r);
    tree[k].sum=tree[k<<].sum+tree[k<<|].sum;
}
void pushdown(int k)
{
    int x=tree[k].r-tree[k].l+;
    tree[k<<].tag+=tree[k].tag;
    tree[k<<|].tag+=tree[k].tag;
    tree[k<<].sum+=(x-(x>>))*tree[k].tag;
    tree[k<<|].sum+=(x>>)*tree[k].tag;
    tree[k].tag=;
}
void upd(int k,int a,int b,int x)
{
    int l=tree[k].l,r=tree[k].r;
    if(a==l && b==r)
    {
        tree[k].tag+=x;
        tree[k].sum+=(b-a+)*x;
        return ;
    }
    if(tree[k].tag) pushdown(k);
    int mid=(l+r)>>;
    if(b<=mid)upd(k<<,a,b,x);
    else if(a>mid)upd(k<<|,a,b,x);
    else upd(k<<,a,mid,x),upd(k<<|,mid+,b,x);
    tree[k].sum=tree[k<<].sum+tree[k<<|].sum;
}
long long ask(int k,int a,int b)
{
    int l=tree[k].l,r=tree[k].r;
    if(a==l && b==r) return tree[k].sum;
    if(tree[k].tag) pushdown(k);
    int mid=(l+r)>>;
    if(b<=mid) return ask(k<<,a,b);
    else if(a>mid) return ask(k<<|,a,b);
    else return (ask(k<<,a,mid)+ask(k<<|,mid+,b));
}

int main()
{
    n=getint();
    for(int i=;i<=n;i++) data[i]=getint();
    build(,,n);
    q=getint();
    while(q--)
    {
        int t,a,b,x;
        t=getint();
        if(t==)
        {
            a=getint();b=getint();x=getint();
            upd(,a,b,x);
        }
        else
        {
            a=getint();b=getint();
            printf("%lld\n",ask(,a,b));
        }
    }
    return ;
}