线段树（Segment Tree）总结

时间：2023-03-09 15:10:14
线段树（Segment Tree）总结

0 写在前面

怎么说呢，其实从入坑线段树一来，经历过两个阶段，第一个阶段是初学阶段，那个时候看网上的一些教学博文和模板入门了线段树，

然后挑选了一个线段树模板作为自己的模板，经过了一点自己的修改，然后就已知用着，其实对线段树理解不深，属于就会套个模板的状态，期间有人问我线段树的问题，我其实也半知不解的，

后来，刷了几道DFS序+线段树的题目，那个时候多多少少有所长进，再次回过头来重新看线段树的代码，理解有所加深，算是勉强理清了线段树这个东西，

再到现在，前不久刚把splay搞完，对平衡二叉搜索树有了更加深的理解，而且线段树相比splay，还是比较简单的，所以终于下定决心，好好整理一下，把线段树这一块理清晰理透彻。

1 线段树模板

2.0 单点修改，区间查询线段树

一开始我没有把这种线段树考虑进来……因为比较简单，有lazy的线段树才是好线段树！

模板可以参见：计蒜客 30996 - Lpl and Energy-saving Lamps

2.1 区间修改，区间求和线段树模板

先是最基础的区间修改，区间求和线段树模板：

#include<bits/stdc++.h>

using namespace std;

const int maxn=+;

int n,a[maxn];

/********************************* Segment Tree - st *********************************/

struct Node{

    int l,r;

    int val,lazy;

    void update(int x)

    {

        val+=(r-l+)*x;

        lazy+=x;

    }

}node[*maxn];

void pushdown(int root)

{

    if(node[root].lazy)

    {

        node[root*].update(node[root].lazy);

        node[root*+].update(node[root].lazy);

        node[root].lazy=;

    }

}

void pushup(int root)

{

    node[root].val=node[root*].val+node[root*+].val;

}

void build(int root,int l,int r) //对区间[l,r]建树

{

    node[root].l=l; node[root].r=r;

    node[root].val=; node[root].lazy=;

    if(l==r) node[root].val=a[l];

    else

    {

        int mid=l+(r-l)/;

        build(root*,l,mid);

        build(root*+,mid+,r);

        pushup(root);

    }

}

void update(int root,int st,int ed,int val) //区间[st,ed]全部加上val

{

    if(st>node[root].r || ed<node[root].l) return;

    if(st<=node[root].l && node[root].r<=ed) node[root].update(val);

    else

    {

        pushdown(root);

        update(root*,st,ed,val);

        update(root*+,st,ed,val);

        pushup(root);

    }

}

int query(int root,int st,int ed) //查询区间[st,ed]的和

{

    if(st>node[root].r || ed<node[root].l) return ;

    if(st<=node[root].l && node[root].r<=ed) return node[root].val;

    else

    {

        pushdown(root);

        int ls=query(root*,st,ed);

        int rs=query(root*+,st,ed);

        pushup(root);

        return ls+rs;

    }

}

/********************************* Segment Tree - ed *********************************/

int main()

{

    int T;

    cin>>T;

    for(int kase=;kase<=T;kase++)

    {

        scanf("%d",&n);

        for(int i=;i<=n;i++) scanf("%d",&a[i]);

        build(,,n);

        printf("Case %d:\n",kase);

        char op[];

        while()

        {

            scanf("%s",op);

            if(op[]=='E') break;

            if(op[]=='A')

            {

                int p,x; scanf("%d%d",&p,&x);

                update(,p,p,x);

            }

            if(op[]=='S')

            {

                int p,x; scanf("%d%d",&p,&x);

                update(,p,p,-x);

            }

            if(op[]=='Q')

            {

                int l,r; scanf("%d%d",&l,&r);

                printf("%d\n",query(,l,r));

            }

        }

    }

}

2.2 原理要点总结

线段树的原理其实很简单，总结来说有下面几个要点：

  1. 把二叉树的节点按从上到下、从左到右存在一个数组里的话，对于每个节点x，它与左右儿子的关系是：左儿子 ls = 2*x，右儿子 rs = 2*x + 1；
  2. 线段树每个节点存储的值是由左右儿子节点的值O(1)得到的；
  3. 每一次区间更新，只对 属于该区间的 又是最靠上层的 的节点进行操作，这个操作有两部分（Node结构体中的成员函数update）：①修改本节点的值，②给本节点打上lazy标记；
  4. lazy标记：某个节点如果打着lazy标记，表明它的儿子们还没有更新；
  5. 每访问到一个节点（不管是更新的访问还是查询的访问），如果要继续深入到其儿子们，显然就要先把lazy标记push下去，一旦push下去就要记得再push上来；

2.3 区间修改，区间最值线段树模板

区间修改，区间最小值线段树模板：

#include<bits/stdc++.h>

using namespace std;

const int maxn=+;

const int INF=0x3f3f3f3f;

int n,a[maxn];

/********************************* Segment Tree - st *********************************/

struct Node{

    int l,r;

    int val,lazy;

    void update(int x)

    {

        val+=x;

        lazy+=x;

    }

}node[*maxn];

void pushdown(int root)

{

    if(node[root].lazy)

    {

        node[root*].update(node[root].lazy);

        node[root*+].update(node[root].lazy);

        node[root].lazy=;

    }

}

void pushup(int root)

{

    node[root].val=min(node[root*].val,node[root*+].val);

}

void build(int root,int l,int r) //对区间[l,r]建树

{

    node[root].l=l; node[root].r=r;

    node[root].val=; node[root].lazy=;

    if(l==r) node[root].val=a[l];

    else

    {

        int mid=l+(r-l)/;

        build(root*,l,mid);

        build(root*+,mid+,r);

        pushup(root);

    }

}

void update(int root,int st,int ed,int val) //区间[st,ed]全部加上val

{

    if(st>node[root].r || ed<node[root].l) return;

    if(st<=node[root].l && node[root].r<=ed) node[root].update(val);

    else

    {

        pushdown(root);

        update(root*,st,ed,val);

        update(root*+,st,ed,val);

        pushup(root);

    }

}

int query(int root,int st,int ed) //查询区间[st,ed]的最小值

{

    if(st>node[root].r || ed<node[root].l) return INF;

    if(st<=node[root].l && node[root].r<=ed) return node[root].val;

    else

    {

        pushdown(root);

        int ls=query(root*,st,ed);

        int rs=query(root*+,st,ed);

        pushup(root);

        return min(ls,rs);

    }

}

/********************************* Segment Tree - ed *********************************/

int main()

{

    memset(a,,sizeof(a));

    n=;

    build(,,n);

    update(,,,);

    for(int i=;i<=n;i++) cout<<query(,i,i)<<" "; cout<<endl;

    cout<<query(,,n)<<endl;

    update(,,,-);

    for(int i=;i<=n;i++) cout<<query(,i,i)<<" "; cout<<endl;

    cout<<query(,,n)<<endl;

}

区间修改，区间最大值线段树模板：

#include<bits/stdc++.h>

using namespace std;

const int maxn=+;

const int INF=0x3f3f3f3f;

int n,a[maxn];

/********************************* Segment Tree - st *********************************/

struct Node{

    int l,r;

    int val,lazy;

    void update(int x)

    {

        val+=x;

        lazy+=x;

    }

}node[*maxn];

void pushdown(int root)

{

    if(node[root].lazy)

    {

        node[root*].update(node[root].lazy);

        node[root*+].update(node[root].lazy);

        node[root].lazy=;

    }

}

void pushup(int root)

{

    node[root].val=max(node[root*].val,node[root*+].val);

}

void build(int root,int l,int r) //对区间[l,r]建树

{

    node[root].l=l; node[root].r=r;

    node[root].val=; node[root].lazy=;

    if(l==r) node[root].val=a[l];

    else

    {

        int mid=l+(r-l)/;

        build(root*,l,mid);

        build(root*+,mid+,r);

        pushup(root);

    }

}

void update(int root,int st,int ed,int val) //区间[st,ed]全部加上val

{

    if(st>node[root].r || ed<node[root].l) return;

    if(st<=node[root].l && node[root].r<=ed) node[root].update(val);

    else

    {

        pushdown(root);

        update(root*,st,ed,val);

        update(root*+,st,ed,val);

        pushup(root);

    }

}

int query(int root,int st,int ed) //查询区间[st,ed]的最大值

{

    if(st>node[root].r || ed<node[root].l) return -INF;

    if(st<=node[root].l && node[root].r<=ed) return node[root].val;

    else

    {

        pushdown(root);

        int ls=query(root*,st,ed);

        int rs=query(root*+,st,ed);

        pushup(root);

        return max(ls,rs);

    }

}

/********************************* Segment Tree - ed *********************************/

int main()

{

    memset(a,,sizeof(a));

    n=;

    build(,,n);

    update(,,,);

    for(int i=;i<=n;i++) cout<<query(,i,i)<<" "; cout<<endl;

    cout<<query(,,n)<<endl;

    update(,,,-);

    for(int i=;i<=n;i++) cout<<query(,i,i)<<" "; cout<<endl;

    cout<<query(,,)<<endl;

    cout<<query(,,n)<<endl;

}

2 线段树的变化与应用

2.1 线段树+DFS序

DFS序：

首先对一棵树进行先序遍历，产生一个序列，用一个数组 in[1~n] 存储每个节点在序列里的位置，显然树根是第一个，所以 in[root] = 1；

同时，由于DFS有回溯存在，所以访问完一个节点的所有子节点（直接的或者间接的），会回到当前节点 x，假设回到当前节点前最后一个访问的节点是 y，我们令 out[x] = in[y]；

简单的来说，一棵树进行先序遍历产生一个序列，一个节点 x 其统领的整棵子树在序列上会是一整段区间，而 in[x] 和 out[x] 就是该区间的左右端点。

而线段树配合DFS序，用处就是将“子树修改，子树查询”变成“区间修改，区间查询”，具体请看下面两篇博文：

HDU 5692 - Snacks：http://www.cnblogs.com/dilthey/p/8988368.html

CodeForces 838B - Diverging Directions：http://www.cnblogs.com/dilthey/p/9005129.html

2.2 加乘线段树

顾名思义，就是可以同时完成如下操作的线段树：

  1. 某区间所有数全部加上某个数；
  2. 某区间所有数全部乘上某个数；
  3. 查询某区间所有数之和；

具体代码直接看题目：Luogu 3373

同时还有进阶版：HDU 4578

2.3 线段树+扫描线

求多个矩形的面积并：HDU 1542

求长方体3次及以上体积交：HDU 3642

2.4 线段树优化Dijkstra算法

主要体现了线段树能够适用的场合之广泛。

详见：单源最短路进阶 - “旧王已死，新王当立！” —— 线段树优化Dijkstra算法

相关文章