线段树-1

· · 题解

线段树

简述

线段树博客
如图，将一个线性区间建成一棵树。


可以实现区间修改，以及区间查询。

建树

记录目前节点，以及目前区间；
将懒标签初始化为0，从高到低进建树。 

void tb(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;
    tb(p/2,l,mid);
    tb(p/2+1,mid+1,r);//一分为二，递归儿子
    ans[p]=ans[p/2]+ans[p/2+1];//更新父亲
}

由二叉树的性质可知，一个节点 i 的儿子分别是 i*2 （左儿子）和 i*2+1 （右儿子）。
于是一分为二，从左右儿子继续递归。
递归完成后，要将左右儿子的区间和加给父亲。

区间加

从根开始，找所求区间并加 k 。

void upd(long ll,long long rr,long long l,long long r,long long p,long long k)
{
    if(ll<=l&&rr>=r)//匹配吗？
    {
        ans[p]+=k*(r-l+1);
        tag[p]+=k;
        return ;
    }
    pd(p,l,r);//传递懒标签
    long long mid=(l+r)/2;
    if(ll<=mid)//向下递归儿子
    {
        upd(ll,rr,l,mid,p*2,k);
    }
    if(rr>mid)
    {
        upd(ll,rr,mid+1,r,p*2+1,k);
    }
    ans[p]=ans[p*2]+ans[p*2+1];
}

先要判断节点对应的区间是否符合要求，然后进行push_down操作，即：

void pd(long long p,long long l,long long r)
{
    long long mid=(l+r)/2;
    f(p*2,l,mid,tag[p]);//传递给两个儿子
    f(p*2+1,mid+1,r,tag[p]);
    tag[p]=0;//reset懒标签
}

也就是说，push_down把祖先的懒标签向下传递。

f：
本质上就是把懒标签（记录在公共祖先上的增加值）和ans（区间和）更新一下

void f(long long p,long long l,long long r,long long k)
{
    tag[p]+=k;
    ans[p]+=k*(r-l+1);
}

区间查询

运行方式和区间加一样，从根节点出发，不过不用修改，而是把符合的区间和加入 res 。

long long qu(long long qx,long long qy,long long l,long long r,long long p)
{
    long long res=0;
    if(qx<=l&&qy>=r)//匹配吗？
    {
        return ans[p];
    }
    long long mid=(l+r)/2;
    pd(p,l,r);//懒标签
    if(qx<=mid)//递归儿子并加入res
    {
        res+=qu(qx,qy,l,mid,p*2);
    }
    if(qy>mid)
    {
        res+=qu(qx,qy,mid+1,r,p*2+1);
    }
    return res;
}

模板

题目见P3372
标程： 

#include<bits/stdc++.h>
using namespace std;

const int N=4e5+7;

long long n,m,op,s,b,c;
long long a[N],ans[N],tag[N];

void tb(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;
    tb(p*2,l,mid);
    tb(p*2+1,mid+1,r);
    ans[p]=ans[p*2]+ans[p*2+1];
}

void f(long long p,long long l,long long r,long long k)
{
    tag[p]+=k;
    ans[p]+=k*(r-l+1);
}

void pd(long long p,long long l,long long r)
{
    long long mid=(l+r)/2;
    f(p*2,l,mid,tag[p]);
    f(p*2+1,mid+1,r,tag[p]);
    tag[p]=0;
}

void upd(long ll,long long rr,long long l,long long r,long long p,long long k)
{
    if(ll<=l&&rr>=r)
    {
        ans[p]+=k*(r-l+1);
        tag[p]+=k;
        return ;
    }
    pd(p,l,r);
    long long mid=(l+r)/2;
    if(ll<=mid)
    {
        upd(ll,rr,l,mid,p*2,k);
    }
    if(rr>mid)
    {
        upd(ll,rr,mid+1,r,p*2+1,k);
    }
    ans[p]=ans[p*2]+ans[p*2+1];
}

long long qu(long long qx,long long qy,long long l,long long r,long long p)
{
    long long res=0;
    if(qx<=l&&qy>=r)
    {
        return ans[p];
    }
    long long mid=(l+r)/2;
    pd(p,l,r);
    if(qx<=mid)
    {
        res+=qu(qx,qy,l,mid,p*2);
    }
    if(qy>mid)
    {
        res+=qu(qx,qy,mid+1,r,p*2+1);
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    tb(1,1,n);
    while(m--)
    {
        cin>>op;
        cin>>s>>b;
        if(op==1)
        {
            cin>>c;
            upd(s,b,1,n,1,c);
        }
        else
        {
            cout<<qu(s,b,1,n,1)<<endl;
        }
    }
    return 0;
}