线段树(Segment Tree)

阅读本文基础知识：二分思想，二叉树，位运算。

本文适用于解决Luogu P3372

代码：

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll ans[1000010],tag[1000010],a[1000010],n,m;
//ans为各节点保存值，tag为各节点的lazy标记，a为各节点初始值
inline ll ls(ll p){
    return p<<1;//求左儿子的编号
}
inline ll rs(ll p){
    return p<<1|1;//求右儿子的编号
}
inline void push_up(ll p){
    ans[p]=ans[ls(p)]+ans[rs(p)];//更新p的保存值为p的左儿子保存值加上p的右儿子保存值
}
void build(ll p,ll l,ll r){
    tag[p]=0;//初始化lazy标记
    if(l==r)//递归边界
    {
        ans[p]=a[l];//初始化p的保存值
        return;
    }
    ll mid=(l+r)>>1;
    build(ls(p),l,mid);//构建左子树
    build(rs(p),mid+1,r);//构建右子树
    push_up(p);//求和，作为p的保存值
}
inline void f(ll p,ll l,ll r,ll k){
    ans[p]+=k*(r-l+1);//更新p的保存值为原值加上该区间长度乘以变化量
    tag[p]+=k;//更新lazy标记
}
inline void push_down(ll p,ll l,ll r){
    ll mid=(l+r)>>1;
    f(ls(p),l,mid,tag[p]);
    f(rs(p),mid+1,r,tag[p]);
    tag[p]=0;//重置lazy标记
}
void update(ll x,ll y,ll l,ll r,ll p,ll k){
    if(x<=l&&r<=y)//递归边界
    {
        ans[p]+=k*(r-l+1);//更新p的保存值为原值加上该区间长度乘以变化量
        tag[p]+=k;//更新lazy标记
        return;
    }
    push_down(p,l,r);//下放lazy标记
    ll mid=(l+r)>>1;
    if(x<=mid) update(x,y,l,mid,ls(p),k);//如果所求区间左端点小于当前区间中点，则所求区间与当前区间的左半区间仍然有重叠，需要更新左子树
    if(y>mid) update(x,y,mid+1,r,rs(p),k);//若...（参照左子树说明），更新右子树
    push_up(p);//求和
}
ll query(ll x,ll y,ll l,ll r,ll p){
    ll tmp=0,mid=(l+r)>>1;
    if(x<=l&&r<=y) return ans[p];//递归边界
    push_down(p,l,r);//下放lazy标记
    if(x<=mid) tmp+=query(x,y,l,mid,ls(p));//若...（参照update里的说明），对左子树求和
    if(y>mid) tmp+=query(x,y,mid+1,r,rs(p));//同上，对右子树求和
    return tmp;
}
int main()
{
    ll x,y,k,t;
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);//建树
    while(m--)
    {
        scanf("%lld",&t);
        switch(t)
        {
            case 1:
            {
                scanf("%lld %lld %lld",&x,&y,&k);
                update(x,y,1,n,1,k);//更新
                break;
            }
            case 2:
            {
                scanf("%lld %lld",&x,&y);
                printf("%lld\n",query(x,y,1,n,1));//求值
                break;
            }
        }
    }
    return 0;
}

对于递归边界的说明：

1. l==r

   我们在build函数中，用[l,r]表示一段区间，显然l==r时该区间内只有一个元素，故可以直接返回。所以此处以l==r作为递归边界。

2. x<=l&&r<=y

   在此种情况中，[x,y]表示所求区间，[l,r]表示当前通过递归来到的区间。若满足x<=l&&r<=y，则表示[l,r]完全包含于[x,y]内部，此时不论如何二分递归[l,r]，子区间都是完全包含于[x,y]内部的，故可以直接返回。所以此处以x<=l&&r<=y作为递归边界。

给萌新看的代码：

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
long long ans[1000010],tag[1000010],a[1000010],n,m;
long long ls(long long p){
    return p*2;
}
long long rs(long long p){
    return p*2+1;
}
void push_up(long long p){
    ans[p]=ans[ls(p)]+ans[rs(p)];
}
void build(long long p,long long l,long long r){
    tag[p]=0;
    if(l==r)
    {
        ans[p]=a[l];
        return;
    }
    long long mid=(l+r)/2;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void f(long long p,long long l,long long r,long long k){
    ans[p]+=k*(r-l+1);
    tag[p]+=k;
}
void push_down(long long p,long long l,long long r){
    long long mid=(l+r)/2;
    f(ls(p),l,mid,tag[p]);
    f(rs(p),mid+1,r,tag[p]);
    tag[p]=0;
}
void update(long long x,long long y,long long l,long long r,long long p,long long k){
    if(x<=l&&r<=y)
    {
        ans[p]+=k*(r-l+1);
        tag[p]+=k;
        return;
    }
    push_down(p,l,r);
    long long mid=(l+r)/2;
    if(x<=mid) update(x,y,l,mid,ls(p),k);
    if(y>mid) update(x,y,mid+1,r,rs(p),k);
    push_up(p);
}
long long query(long long x,long long y,long long l,long long r,long long p){
    long long tmp=0,mid=(l+r)/2;
    if(x<=l&&r<=y) return ans[p];
    push_down(p,l,r);
    if(x<=mid) tmp+=query(x,y,l,mid,ls(p));
    if(y>mid) tmp+=query(x,y,mid+1,r,rs(p));
    return tmp;
}
int main()
{
    long long x,y,k,t;
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--)
    {
        scanf("%lld",&t);
        switch(t)
        {
            case 1:
            {
                scanf("%lld %lld %lld",&x,&y,&k);
                update(x,y,1,n,1,k);
                break;
            }
            case 2:
            {
                scanf("%lld %lld",&x,&y);
                printf("%lld\n",query(x,y,1,n,1));
                break;
            }
        }
    }
    return 0;
}