线段树：Segment Tree(单点修改/区间修改模板) C++

线段树是非常有效的数据结构，可以快速的维护单点修改，区域修改，查询最大值，最小值等功能。

同时，它也很重要。如果有一天比赛，你卡在了一道线段树模板题目上，这就真的尴尬了。不过，随着时代的进步，题目也越来越变态，线段树更多时候则是你算法时间复杂度的优化。

这是单点查询的代码。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int n;
int a[100005];

struct node
{
    int l;
    int r;
    int sum;
} t[400005];

void build (int i,int l,int r)
{
    t[i].l=l;
    t[i].r=r;
    int mid=l+r>>1;
    if (l==r) 
    {
        t[i].sum=a[l];return ;
    }
    
    build(i<<1,l,mid);
    build((i<<1)+1,mid+1,r);
    
    t[i].sum=t[i<<1].sum+t[(i<<1)+1].sum;
    
    return ;
}

void update(int i,int p,int k)
{
    if (t[i].l==t[i].r) 
    {
        t[i].sum=k;
        return;
    }
    
    int mid=t[i].l+t[i].r>>1;
    if (p<=mid) update(i<<1,p,k);
    if (p>mid) update((i<<1)+1,p,k);
    t[i].sum=t[i<<1].sum+t[(i<<1)+1].sum;
    
    return ;
}

int getsum(int i,int l,int r)
{
    int mid=(t[i].l+t[i].r)>>1;
    if (l<=t[i].l&&t[i].r<=r) return t[i].sum;
    if (r<=mid) return getsum(i<<1,l,r);
    if (l>mid) return getsum((i<<1)+1,l,r);
    
    return getsum(i<<1,l,r)+getsum((i<<1)+1,l,r);
}

int main()
{
    int m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    while (m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if (x==1)
        {
            update(1,y,z);
        }
        else printf("%d
",getsum(1,y,z));
    }
    
    return 0;
}

下面是区间修改的代码。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
using namespace std;

struct node
{
    int l,r,s,d;
} t[50005];
int n,m;
int a[10005];

void pushup(int x)
{
    t[x].s=t[x<<1].s+t[(x<<1)+1].s;
    return;
}

void pushdown(int x)
{
    int mid=(t[x].l+t[x].r)>>1;
    int d=t[x].d;
    t[x<<1].d+=d;t[(x<<1)+1].d+=d;
    t[x<<1].s+=(mid-t[x].l+1)*d;
    t[(x<<1)+1].s+=(t[x].r-mid)*d;
    return;
}

void build(int i,int l,int r)
{
    t[i].l=l;
    t[i].r=r;
    t[i].d=0;
    if (l==r)
    {
        t[i].s=a[l];
        return ;
    }
    
    int mid=l+r>>1;
    
    build(i<<1,l,mid);
    build((i<<1)+1,mid+1,r);
    
    pushup(i);
    return;    
}

int getsum(int i,int l,int r)
{
    int mid=t[i].l+t[i].r>>1;
    if (l<=t[i].l&&t[i].r<=r)
    {
        return t[i].s;
    }
    int d=t[i].d;
    if (!d) pushdown(i);
    int ret=0;
    if (mid>=l) ret+=getsum(i<<1,l,r);
    if (mid<r) ret+=getsum((i<<1)+1,l,r);
    
    return ret;
}

void update(int i,int l,int r,int del)
{
    if (t[i].l==t[i].r) 
    {
        t[i].d+=del;
        t[i].s+=(t[i].l-t[i].r+1)*del;
        return ;
    }
    
    int mid=t[i].l+t[i].r>>1;
    if (!t[i].d) pushdown(i);
    if (mid>=l) update(i<<1,l,r,del);
    if (mid<r) update((i<<1)+1,l,r,del); 
    pushup(i);
}


int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    build (1,1,n);
    
    for (int i=1;i<=m;i++)
    {
        int x,y,z,d;
        scanf("%d",&x);
        if (x==1)
        {
            scanf("%d%d%d",&y,&z,&d);
            update(1,y,z,d);
        }
        if (x==2)
        {
            scanf("%d%d",&y,&z);
            printf("%d
",getsum(1,y,z));
        }
    }
    
    return 0;
}