不同思路的线段树整理

Rain_142857 · 2018-11-06 14:14:51 · 个人记录

引言

线段树是一种非常优秀的数据结构，可以处理各种各样的区间操作。有一句“名言”说得好啊，线段树就是分治思想的树化，这点可以等到我们讲到后面再慢慢体会。关于基本的线段树结构、思想以及具体可实现的操作、为什么要执行这些操作，这里不再详细讲解，各位大佬讲得通俗易懂，而本文的目的是整理一下不同思路产生的普通线段树（蒟蒻学的东西不多，高级线段树如zkw线段树等不会啊qwq）的两种不同写法，并比较他们的优劣性。

1.线段树的基本功能

这是我们分析接下来问题的基本套路，也在此总结一下普通线段树的基本功能，如果看这篇文章的你还没有学过线段树，请左转各位大佬写的线段树全解qwq~

线段树由于所解决问题的不同会有不同的形式，本文所创设的题目背景是洛谷P3372，即区间加值、区间求和。以下在第4章节前的所有关于代码的解释，全部都围绕着这个问题来展开。

首先，对于线段树，我们需要一个特殊的结构体数组来维护：

struct node
{
    int lf;//当前结点所表示区间的左端点
    int ri;//当前结点所表示区间的右端点
    long long sum;//当前结点所表示区间的区间和
    long long tag;//当前结点的加法意义lazy_tag(如果不懂什么是lazy_tag，请右转各位大佬的线段树全解qwq~)
}t[4*maxn+10];

众所周知，线段树是一棵二叉树，所以我们可以写一个函数来表示左右儿子的下标（个人习惯写成函数，其实如果变量名统一的话可以写成define~）：

int ls(int k)//结点k的左儿子下标
{
    return k<<1;//位运算，相当于k*2，相比较之下位运算应该要快一点点
}
int rs(int k)//结点k的右儿子下标
{
    return k<<1|1;//位运算，相当于k*2+1
}

然后，我们需要一个更新sum值的操作，称为update。

然后，我们需要基本的建树操作（维护父子关系），称为build。

然后，我们需要下放标记的操作，称为pushdown。

然后，对于区间修改（本题中为区间加值），我们需要一个操作称为addval。

最后，区间询问（本题中为区间求和）操作，我们称为query。

不同思路之下，update、build、pushdown、addval、query五个操作各有各的写法，但是最终实现的功能都是一样的。从第二章开始，我们逐个介绍不同思路下这五种操作的写法。

2.以树上结点所表示的区间为基准的线段树

实现普通线段树的第一种思路：在更新维护和查找的时候，以树上结点所维护的区间为基准进行动态维护、查询。

核心思想

以树上结点所维护的区间为基准，那么就要在动态维护和查找的时候，判断当前所查询区间和当前结点所维护区间的关系。（控制后者不变，改变前者）

update操作的实现

t[pos].sum=t[ls(pos)].sum+t[rs(pos)].sum+t[pos].tag*(t[pos].ri-t[pos].lf+1);

很简单的一句话，意思是当前结点的区间和等于左儿子的区间和+右儿子的区间和+自己所维护的加法标记*自己所维护的区间长度。挺好理解的吧qwq~

因为update操作只有一行，所以写不写成函数都无所谓。在第二章里我们不写成函数，看这篇文章的你一定要能认出来这句话是update操作；在第三章里我们写成函数。

pushdown操作的实现

下放标记的时候，一定记得更新（调用update操作）。

void pushdown(int pos)
{
    //给左儿子下放标记
    t[pos*2].tag+=t[pos].tag;
    t[pos*2].sum=t[pos*2].sum+t[pos].tag*(t[pos*2].ri-t[pos*2].lf+1);//这是update操作（简化版）
    //给右儿子下放标记
    t[pos*2+1].tag+=t[pos].tag;
    t[pos*2+1].sum=t[pos*2+1].sum+t[pos].tag*(t[pos*2+1].ri-t[pos*2+1].lf+1);//这是update操作（简化版）
    //把当前节点的lazy_tag清空
    t[pos].tag=0ll;
    return;
}

可能你会问这样一个问题：为什么只更新左右儿子的sum值而不更新当前结点的sum值呢？这是因为，下放标记仅仅是下放标记，我们没有对当前结点所维护的区间的值进行修改，区间的值没有被修改的时候，区间和——当前结点（两个儿子的父亲结点）的sum值——当然也不会被修改啊~

build操作的实现

先上代码：

void build(int pos,int lb,int rb)
{
    int mid=(lb+rb)/2;
    t[pos].lf=lb;
    t[pos].ri=rb;
    t[pos].tag=0ll;
    //如果发现当前结点是叶子结点
    if(lb==rb)
    {
        t[pos].sum=((long long)(a[lb]));
        return;
    }
    //如果不是叶子结点，递归左右儿子
    build(pos*2,lb,mid);
    build(pos*2+1,mid+1,rb);
    //update操作（非常重要！！！）
    t[pos].sum=t[pos*2].sum+t[pos*2+1].sum;//因为刚刚建树，所以lazy_tag为0，没有必要加上
    return;
}

这段代码也比较好理解，pos就是当前结点的编号，lb就是当前结点所维护区间的左端点，rb就是右端点。如果发现当前结点是叶子结点，结点的值（t[pos].sum）就是原序列里对应位置上的值（a[lb]或a[rb]）。如果不是叶子结点意味着当前结点有两个儿子，那么递归处理，递归完了一定记得要update！递归完了一定记得要update！递归完了一定记得要update！重要的事情说三遍，这个真的很重要！很容易漏！

关键我们来看addval和query两个操作。

addval操作的实现

对于一个待处理的区间，它和当前的树上结点有4中可能的关系：

图示应该比较清楚，那么直接上代码：

void addval(int pos,int lb,int rb,int v)
{
    int mid=(t[pos].lf+t[pos].ri)/2;
    //case 1:待操作区间刚好就是当前区间
    if(lb==t[pos].lf&&rb==t[pos].ri)
    {
        t[pos].tag+=v;//修改当前结点lazy_tag
        t[pos].sum=t[pos].sum+v*(t[pos].ri-t[pos].lf+1);//这是update操作
        return;
    }
    //如果事情并不那么完美
    pushdown(pos);//VERY IMPORTANT
    //case 2:待操作区间完全被包含在左儿子里
    if(rb<=mid)addval(pos*2,lb,rb,v);
    //case 3:待操作区间完全被包含在右儿子里
    else if(lb>=mid+1)addval(pos*2+1,lb,rb,v);
    //case 4:待操作区间跨了左右两个儿子区间
    else
    {
        addval(pos*2,lb,mid,v);
        addval(pos*2+1,mid+1,rb,v);
    }
    //递归处理之后记得更新(VERY IMPORTANT)
    t[pos].sum=t[pos*2].sum+t[pos*2+1].sum;//这是update操作
    return;
}

可能你会问这样一个问题：当当前结点是叶子结点的时候，没有左右儿子，怎么递归？其实啊，如果当前结点是叶子结点，那么当前的待操作区间也一定变成了原序列里的一个元素，也就一定刚好是当前结点所维护的整个区间，也就一定会终止递归。

query操作的实现

同样的思路，我们来看最后一个重要功能——区间查询的实现：

图示也应该比较清楚，我们也直接上代码：

long long query(int pos,int lb,int rb)
{
    int mid=(t[pos].lf+t[pos].ri)/2;
    //case 1:刚好是当前的整个区间
    if(lb==t[pos].lf&&rb==t[pos].ri)
    {
        return t[pos].sum;
    }
    //如果事情并不总是这么完美
    pushdown(pos);//VERY IMPORTANT
    //case 2:待查询区间完全被包含在左儿子区间里
    if(rb<=mid)return query(pos*2,lb,rb);
    //case 3:待查询区间完全被包含在右儿子区间里
    else if(lb>=mid+1)return query(pos*2+1,lb,rb);
    //case 4:待查询区间跨左右两个儿子的区间
    else return query(pos*2,lb,mid)+query(pos*2+1,mid+1,rb);
}

你可能又会问这样一个问题：为什么最后没有update操作了呢？这是因为，第一，函数以return作为结束的标志，把update加在return之后这句话不会被执行；第二，我们并没有修改任何一个元素，所以无需更新。

思路一总结

以树上结点所维护的区间为基准，这样的线段树写出来非常整齐，每一种区间操作函数都是规规整整的八句话（addval和query）——即四种case。这种思路的核心是——动态维护和查找的时候，固定树上结点所维护的区间，改变当前待维护/待查询的区间。有的题目适合使用这种思路的线段树，但是也有相当一部分数量的题目不适合（如果你是调程序高手，那么请无视这句话）。具体我们到第四章节再来讲述。

好了，上思路一完整源代码（luoguP3372AC代码）：

//segmenttree 1:
//range sum problem and modifying
#include<cstdio>
using namespace std;
//point
struct node
{
    int lf,ri;
    long long sum,tag;
}t[400010];
//initial array
int a[100010];
//build
void build(int pos,int lb,int rb)
{
    int mid=(lb+rb)/2;
    t[pos].lf=lb;
    t[pos].ri=rb;
    //leaf point
    if(lb==rb)
    {
        t[pos].sum=((long long)(a[lb]));
        return;
    }
    //recursion
    build(pos*2,lb,mid);
    build(pos*2+1,mid+1,rb);
    //update
    t[pos].sum=t[pos*2].sum+t[pos*2+1].sum;
    return;
}
//pushdown tag
void pushdown(int pos)
{
    //pushdown to leftson
    t[pos*2].tag+=t[pos].tag;
    t[pos*2].sum=t[pos*2].sum+t[pos].tag*(t[pos*2].ri-t[pos*2].lf+1);
    //pushdown to rightson
    t[pos*2+1].tag+=t[pos].tag;
    t[pos*2+1].sum=t[pos*2+1].sum+t[pos].tag*(t[pos*2+1].ri-t[pos*2+1].lf+1);
    //set the current point's tag to 0
    t[pos].tag=0ll;
    return;
}
//modify an interval
void addval(int pos,int lb,int rb,int v)
{
    int mid=(t[pos].lf+t[pos].ri)/2;
    //case 1:exactly the same interval
    if(lb==t[pos].lf&&rb==t[pos].ri)
    {
        t[pos].tag+=v;
        t[pos].sum=t[pos].sum+v*(t[pos].ri-t[pos].lf+1);
        return;
    }
    //otherwise
    pushdown(pos);//VERY IMPORTANT
    //case 2:all in leftson
    if(rb<=mid)addval(pos*2,lb,rb,v);
    //case 3:all in rightson
    else if(lb>=mid+1)addval(pos*2+1,lb,rb,v);
    //case 4:in both leftson and rightson
    else
    {
        addval(pos*2,lb,mid,v);
        addval(pos*2+1,mid+1,rb,v);
    }
    //update at last(VERY IMPORTANT)
    t[pos].sum=t[pos*2].sum+t[pos*2+1].sum;
    return;
}
long long query(int pos,int lb,int rb)
{
    int mid=(t[pos].lf+t[pos].ri)/2;
    //case 1:exactly the same interval
    if(lb==t[pos].lf&&rb==t[pos].ri)
    {
        return t[pos].sum;
    }
    //otherwise
    pushdown(pos);//VERY IMPORTANT
    //case 2:all in leftson
    if(rb<=mid)return query(pos*2,lb,rb);
    //case 3:all in rightson
    else if(lb>=mid+1)return query(pos*2+1,lb,rb);
    //case 4:in both leftson and rightson
    else return query(pos*2,lb,mid)+query(pos*2+1,mid+1,rb);
}
int main()
{
    int n,m,i,j,k,p,x,y,z;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    build(1,1,n);
    for(i=1;i<=m;i++)
    {
        scanf("%d",&p);
        if(p==1)
        {
            scanf("%d%d%d",&x,&y,&z);
            addval(1,x,y,z);
        }
        else if(p==2)
        {
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(1,x,y));
        }
    }
    return 0;
}

用时: 538ms / 内存: 7188KB ，详情见R10317756。

3.以所查询区间为基准的线段树

本来思路一（第2章所讲）的线段树我觉得挺好的，但是在这个秋天，蒟蒻刷了一道神题之后，果断放弃了思路一而改用思路二，为什么呢？先看完第3章，然后我们再来聊这道神题。

核心思想

以所查询区间为基准，那么就要在动态维护和查找的时候，判断当前结点所维护区间和所查询区间的关系。（也是控制后者不变，改变前者）

update操作的实现

也是很简单的一句话，我们写成函数（之前告诉过你的）。

void update(int k)
{
    t[k].sum=t[ls(k)].sum+t[rs(k)].sum;
}

但是细心的你一定发现了——为什么这次没有处理标记的问题？不处理的话怎样调用？调用的时候是否要加上一些新的操作？这是一个小小的优化（思路一同样适用的），不理解不要紧，先往下看到addval操作，在那里我们将会解释update这样写的原因，你就会明白了。

pushdown操作的实现

下放标记代码：

void pushdown(int k)
{
    if(t[k].tag)//what's this?
    {
        //下放给左儿子
        t[ls(k)].tag+=t[k].tag;
        t[ls(k)].sum+=(t[ls(k)].ri-t[ls(k)].lf+1)*t[k].tag;
        //下放给右儿子
        t[rs(k)].tag+=t[k].tag;
        t[rs(k)].sum+=(t[rs(k)].ri-t[rs(k)].lf+1)*t[k].tag;
        //清空当前结点的lazy_tag
        t[k].tag=0ll;
    }
    return;
}

细心的你又发现了：那句打上了//what's this?注释的话是什么意思呢？原来啊，这又是一个小小的优化（思路一同样适用），但是快不了多少，如果tag不为零就下放，如果tag已经是零了，就不用下放了，因为下放也是+0。为什么说这个优化快不了多少，加不加无所谓呢？因为pushdown操作是线性的，几乎不增加时间复杂度。

build操作的实现

还是先上代码：

void build(int k,int lb,int rb)
{
    t[k].lf=lb;
    t[k].ri=rb;
    //如果发现是叶子结点
    if(lb==rb)
    {
        t[k].sum=a[lb];
        t[k].tag=0ll;
        return;
    }
    //如果不是叶子结点，意味着有两个儿子，那么分别递归处理
    int mid=(lb+rb)>>1;
    build(ls(k),lb,mid);
    build(rs(k),mid+1,rb);
    t[k].tag=0ll;
    update(k);//仍然非常重要
    return;
}

build操作几乎无改动，细心的你又问了：为什么刚才的update操作没有处理标记，这里调用的时候也不需要添加更多的操作呢？请你回看第二章的build操作，在那里代码上的update操作那句话后面有一小行注释。注释是这样写的：

t[pos].sum=t[pos*2].sum+t[pos*2+1].sum;//因为刚刚建树，所以lazy_tag为0，没有必要加上

现在你明白了吗？建树的时候根本不需要处理标记。

addval操作的实现

重点：思路二的核心思想是控制操作区间不变，改变操作的树上结点。

还有一个重点：线段树中，我们只能对一个树上结点所维护的区间里所有的元素进行一次性操作。

对于树上某一结点所维护的区间，它和我们要操作的区间可能有4种关系：

图示也比较清楚吧，下面上代码，如果你到此为止不理解思路二的清晰性，那么代码说明一切：

void addval(int k,int lb,int rb,long long v)
{
    //case1:
    if(lb<=t[k].lf&&rb>=t[k].ri)
    {
        t[k].tag+=v;
        t[k].sum+=v*(t[k].ri-t[k].lf+1);//※
        return;
    }
    //case2|case3|case4(可以合起来写成下面的样子，这样的if,if实际上是四重分治，理解一下为什么)
    int mid=(t[k].lf+t[k].ri)>>1;
    pushdown(k);//别丢掉！！
    //和左儿子有交集
    if(lb<=mid)
    {
        addval(ls(k),lb,rb,v);
    }
    //和右儿子有交集
    if(rb>=mid+1)
    {
        addval(rs(k),lb,rb,v);
    }
    update(k);//？？
    return;
}

接下来解释update操作那样写的原因及调用的特殊方法。

我们递归处理的实质是，先找到问题的根源（走基层/递归之"递"），然后再层层回溯到最终的大问题本身（跳上级/递归之"归"）。

现在你明白了吗？如果不明白，就把图片中蓝色的话多读几遍。你应该会明白的。

query操作的实现

与addval相同的思路，我们来看区间查询query操作。

和addval思路完全相同，我们来看代码吧，代码用了一个非常巧妙的转化，避免了函数在return提前结束的尴尬：

long long query(int k,int lb,int rb)
{
    //case 1:
    if(lb<=t[k].lf&&rb>=t[k].ri)
    return t[k].sum;
    //case2|case3|case4
    int mid=(t[k].lf+t[k].ri)>>1;
    long long ans=0ll;
    pushdown(k);//别掉了
    if(lb<=mid)
    {
        ans+=query(ls(k),lb,rb);
    }
    if(rb>=mid+1)
    {
        ans+=query(rs(k),lb,rb);
    }
    return ans;
}

思路二总结

以所查询区间为基准的线段树最大的优点就是所查询区间在递归前后始终不变。

在大部分题目中，思路二写出来的代码明显优于思路一。但是有的脑洞题，思路一会变得较好。

贴出思路二的完整源代码（同样luoguP3372AC代码）：

#include<cstdio>
using namespace std;
int ls(int k)
{
    return k<<1; 
} 
int rs(int k)
{
    return k<<1|1; 
} 
struct node
{
    int lf,ri;
    long long sum;
    long long tag;
}t[800010];
long long a[100010];
void update(int k)
{
    t[k].sum=t[ls(k)].sum+t[rs(k)].sum;
}
void pushdown(int k)
{
    if(t[k].tag)
    {
        t[ls(k)].tag+=t[k].tag;
        t[ls(k)].sum+=(t[ls(k)].ri-t[ls(k)].lf+1)*t[k].tag;
        t[rs(k)].tag+=t[k].tag;
        t[rs(k)].sum+=(t[rs(k)].ri-t[rs(k)].lf+1)*t[k].tag;
        t[k].tag=0ll;
    }
    return;
}
void build(int k,int lb,int rb)
{
    t[k].lf=lb;
    t[k].ri=rb;
    if(lb==rb)
    {
        t[k].sum=a[lb];
        t[k].tag=0ll;
        return;
    }
    int mid=(lb+rb)>>1;
    build(ls(k),lb,mid);
    build(rs(k),mid+1,rb);
    t[k].tag=0ll;
    update(k);
    return;
}
void addval(int k,int lb,int rb,long long v)
{
    if(lb<=t[k].lf&&rb>=t[k].ri)
    {
        t[k].tag+=v;
        t[k].sum+=v*(t[k].ri-t[k].lf+1);
        return;
    }
    int mid=(t[k].lf+t[k].ri)>>1;
    pushdown(k);
    if(lb<=mid)
    {
        addval(ls(k),lb,rb,v);
    }
    if(rb>=mid+1)
    {
        addval(rs(k),lb,rb,v);
    }
    update(k);
    return;
}
long long query(int k,int lb,int rb)
{
    if(lb<=t[k].lf&&rb>=t[k].ri)
    return t[k].sum;
    int mid=(t[k].lf+t[k].ri)>>1;
    long long ans=0ll;
    pushdown(k);
    if(lb<=mid)
    {
        ans+=query(ls(k),lb,rb);
    }
    if(rb>=mid+1)
    {
        ans+=query(rs(k),lb,rb);
    }
    return ans;
}
int main()
{
    int n,m,i,j,k,x,y,z;
    long long val;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    scanf("%lld",&a[i]);
    build(1,1,n);
    for(i=1;i<=m;i++)
    {
        scanf("%d",&x);
        if(x==1)
        {
            scanf("%d%d%lld",&y,&z,&val);
            addval(1,y,z,val);
        }
        else if(x==2)
        {
            scanf("%d%d",&y,&z);
            printf("%lld\n",query(1,y,z));
        }
    }
    return 0;
}

用时: 597ms / 内存: 9860KB ，详情见R13264461。

吁！终于讲完了两种不同思路的线段树~

4.普通线段树两种写法的优劣性比较

思路一的特点是——容易理解，但是写完调不出来。想得少，写得多。

思路二的特点是——代码容易写，但是不是很好理解。想得多，写得少。

线段树思路二的优势体现

我第一次学线段树，就是学的思路一。一开始写得很不熟练，后来反反复复打板子才弄得比较熟练。后来啊，刷一些线段树水题都用思路一，打模拟赛也用思路一，什么事都没有。直到这个秋天，我做到一道神题——线段树2。

两种lazy_tag！！！

我写思路一写了一天，发现样例都没过，然后不断修改，出现各种玄学错误，调程序调了三天，中途还有各位大佬的帮助，终于调了出来。我调的方法是：

• 第一步：在代码编辑器里同时按下Control+A键。

• 第二步：按下Delete键。

• 第三步：按照思路二重写代码。

然后AC。

当两个lazy_tag同时出现的时候，思路二是当仁不让的选择。

线段树思路一的优势体现

那线段树二写得又少，用处又多，思路一是不是就可以被完全抹杀了呢？

其实也不是。刚刚我们就说过，思路一容易理解。再者，思路一在区间合并上有着极大的好处。当没有lazy_tag的时候，我们也可以使用思路一写线段树。看一道题：SPOJ GSS1 Can you answer these queries I | 洛谷链接SP1043。这道题是区间查询最大子段和，使用思路一就比较容易理解，因为这道题涉及多种区间合并（紧靠左端点的最大子段和、紧靠右端点的最大子段和、区间和）而且没有lazy_tag，所以思路一既整齐又好理解，那么使用思路一就不错。当然，思路二也不是不好写。这篇文章不是这题的题解，所以不再赘述详细解法。

后记

很多人会问：线段树的优点在哪？我记上标记，之后不还是要下放！而且待查询区间和树上一个结点所维护的区间重合的概率是多么小！

其实，线段树的优点正在于“先打标记，后下放”这一点。这样的动态数据传输方式，使得一些标记不会被下放到最底层，一些查询也不会跑到最底层，一些操作也不用分成大堆大堆的单点。这个好处在线段树只有几层的情况下是不会显现得那么明显的，但是当这个数据大起来，线段树超过十层甚至二十层的时候，这些少下放的标记、少拆分的单点的数量就会变得相当可观。而且，线段树是一种分治思想的树化，树形结构也能够期望在logn的时间复杂度内快速找到一个子区间在大区间内的准确位置。

但是，线段树也有一定缺点。因为它的建树维护需要区间合并操作，所以符合结合律的维护才能用线段树，这个各位大佬都有提到。

最后，完结撒花~

orz dalao @suncongbo @hanyuwei @linfourxu