线段树进阶

· · 个人记录

说在前面

这里是一些线段树的进阶运用。例题统一放在末尾。主要参考OI Wiki。

线段树的合并与分裂

前面写过合并分裂，这里再更详细的写一下

前置知识：动态开点

动态开点就是在建树过程中，对于需要的点，就构建，而不需要的就不建，这样可以大大节省空间。由于动态开点抛弃了原有的二叉树的节点编号方式，所以需要另外再开ls和rs记录左右节点的编号。动态开点的核心思想就是节点只有在需要时才会被创建。该技巧常在权值线段树上使用，在不可以或不好离散化有必须使用权值线段树时，这是一个不错方法。

int tot=1;
void change(int p,int l,int r,int k){
    if(!p) return ;
    if(l==r) {
        t[p].cnt+=1;
        return ;
    }
    int mid=(l+r)>>1;
    if(k<=mid){
        if(!t[p].ls){
            t[p].ls=++tot;
        }
        change(t[p].ls,l,mid,k);
    }
    else{
        if(!t[p].rs){
            t[p].rs=++tot;
        }
        change(t[p].rs,mid+1,r,k);
    }
    t[p].cnt=t[t[p].ls].cnt+t[t[p].rs].cnt;
}
int query(int p,int l,int r,int k){
    if(!p) return 0;
    if(l==r) return 0;
    int mid=(l+r)>>1;
    if(k<=mid) return t[t[p].rs].cnt+query(t[p].ls,l,mid,k);
    else return query(t[p].rs,mid+1,r,k); 
}

线段树合并

1.知识点来源

现在给定一棵n个节点的树，每个节点都有m种权值，初始为0，每次操作会给路径(u,v)上所有点的第k种权值加上1，求所有操作后每个节点上值最大的权值是第几种。

看到这个问题，首先想到对每个节点都开一个数组记录第i种权值的大小，但是发现空间并不支持这样做，所以需要一种空间占用更小的做法。

2.知识点介绍

线段树合并是一种将两个线段树上每个节点的对应信息合并的算法，合并后会得到一棵线段树，其每个节点都保留了原来两棵树上对应节点的信息并，他常常被用于维护树上或图上的路径问题。由于在大部分情况下，相同位置的信息合并只在数域上有意义，所以线段树合并常和权值线段树一起使用。

对于上面的问题，我们不妨先对修改操作进行差分，化为两个点上的修改，接着建立一棵可以在节点间传递的权值线段树，该线段树的区间[l,r]代表第l到r种权值的值之和，现在我们只需要将节点i所有儿子的信息合并起来，再加上i自己的信息，最后询问[1,n]内的最值即可，这时，我们可以考虑线段树合并。

线段树合并的过程本质上十分暴力。在合并线段树时，我们不可能每次都新建一棵线段树，这样空间会非常炸裂，所以考虑在原来的一棵树上直接进行合并，过程如下：

假设两棵树为A和B，从1开始，现在到了p

如果A或B的这个节点为空，直接返回另一棵树的对应节点。

如果到了叶子节点，合并信息，返回A（B也可以，但是要统一）。

否则继续递归，回溯时更新节点。

int merge(int pa,int pb){
    if(!pa||!pb) return pa+pb;
    if(t[pa].l==t[pa].r){
        ... //do something
        return pa;
    }
    int mid=(t[pa].l+t[pa].r)>>1;
    t[pa].ls=merge(t[pa].ls,t[pb].ls);
    t[pa].rs=merge(t[pa].rs,t[pb].rs);
    pushup(pa);
    return pa;
}

上述过程的复杂度为O(n\log n)，但是考虑到线段树合并常在权值线段树上使用，点集大小远远达不到上限，且一般不会重复合并同一棵树，因此时空复杂度均摊下来总共为O(n\log n)。但是在某些情况下，其他数据结构如平衡树和可并堆为更优选择，需结合题目具体分析。具体证明以引入题为例：

每个节点的线段树合并后都只记录了该节点子树中的所有信息，设节点为p，最坏情况下p子树中所有节点的信息都不同，那么就需要开size_p个节点，所以向上一级的合并为O(size_p\log({size_p}))的，设size_{root}+\frac{size_{root}}{2}+\frac{size_{root}}{4}+...=x，所以合并的总时间为x\log x约为n\log n

在过程中有很多浪费了的空间，可以回收起来再进行利用，在线段树分裂时会讲。

3.注意事项

1.注意空间的分配以及点集的大小，某些情况下使用线段树合并会被卡。

2.注意合并的顺序以及对象，上面代码是将y包含到x上。

3.不要重复合并同一棵树，这回使时间炸裂。

4.回收空间时回收站大小要开够。

4.常见优化应用

空间回收

线段树分裂时讲，能节省较多空间。

线段树分裂

1.知识点来源

给定一个可重数集，现在有四种操作：

1 p s t 将第p个数集中值在[s,t]间的树分离出来，形成一个新数集，为第k+1个数集，k为当前数集数量。

2 p x k 向第p个数集中加入k个x。

3 p t 将第p个数集与第t个数集合并，第t个数集变为空集。

4 p l r 询问第p个数集中值在[l,r]中的数有多少个。

看到上面的问题，假设先不考虑第1个操作，现在有几个数集要执行2,3,4操作，那么我们可以使用线段树合并，建立权值线段树，来描述数集，然后合并操作就是线段树合并。

现在回到操作1，发现分裂其实可以像其他区间操作一样递归，当当前区间被操作区间包含时可以直接断边。这便是线段树分裂

2.知识点介绍

线段树分裂其实是线段树合并的逆过程。线段树分裂只对有序序列有意义，对于无序序列区间并不单调，所以无意义。由于这个性质，线段树分裂常见于权值线段树的维护。

线段树合并和分裂都要进行时注意回收节点，不要出现节点混用/共用的情况。

现在要从管辖区间为[1,n]的线段树上分裂出[s,t]的线段树，过程如下

如果当前区间与[s,t]无交，或为空，则直接return

如果当前区间与[s,t]有部分交或当前区间覆盖[s,t]，则新建节点，并继续递归

如果当前区间被[s,t]覆盖，则直接继承当前区间的信息，当前区间与原树断开边。

容易证明该过程的复杂度是\log n的，因为该区间最多只会断开\log n条边。

void split(int &x,int &y,int l,int r,int s,int t){
    if(l>t||s>r) return ;
    if(!x) return ;
    if(s<=l&&r<=t){
        y=x;
        x=0;
        return ;
    }
    if(!y) y=recycle();
    int mid=(l+r)>>1;
    if(s<=mid) split(t[x].ls,t[y].ls,l,mid,s,t);
    if(t>mid) split(t[x].rs,t[y].rs,mid+1,r,s,t);
    pushup(x),pushup(y);
}

这里说明，由于线段树合并和分裂同时进行时对空间消耗巨大，且会出现点混乱的情况，所以要空间回收。

3.注意事项

1.在分裂和合并同时进行时需要回收空间，以避免点混乱和空间炸裂。

2.分裂时注意if(l>t||s>r) return ;判断，因为有时会神秘的出现这类错误导致RE。

4.常见优化应用

空间回收

建立一个回收站，记录当前空余的位置有哪些，然后在需要时调用，具体代码如下

int recycle(){
    if(top) return recycle_bin[top--];
    else return ++tot;
}

//invoking function
x=recycle()

//recycle a node
recycle_bin[++top]=x;
clear(x)

吉司机线段树

吉司机线段树常被用于处理区间最值操作和查询区间历史最值。

1.知识点来源

引入1

给定一个序列，现在要维护这个序列支持下列操作

1 l r t 将[l,r]内的数变为\min(a_i,t)

2 l r 查询[l,r]内所有数的最大值

3 l r 查询\sum\limits_{i=l}^ra_i

抛开操作1，本题就是一道板子题，现在考虑操作1。处理操作1首先想到维护一个tag，但是发现并不知道那些值会被修改，且不知道变化的值。这时，可以用上吉司机线段树。

引入2

给定一个序列，现在要维护这个序列支持下列操作

1 l r x 将区间[l,r]内的数加上x

2 l r k 求区间[l,r]内比k小的数有多少个

这个问题当然可以使用主席树或平衡树加二分解决，但是这里提供一种玄学的人类智慧做法，其复杂度证明要用到势能分析，本人不会，该做法可以被hack，但是在数据随机的情况下性能优秀。

考虑维护区间的最大值和最小值，修改操作打个标记即可，而查询操作可以这样做

设当前节点为p，管辖区间为[l,r]，询问操作为(L,R,k)

如果当前区间的最大值比k小，说明整个区间满足条件，所以返回\min(r,R)-\max(l,L)+1

如果当前区间的最小值比k大，说明整个区间全部不符合条件，所以返回0

否则继续递归

2.知识点介绍

吉司机线段树其实不是一种新的线段树，他只是一种线段树解决区间最值操作和查询区间历史最值的方法。

看引入1的问题，注意到操作1只会涉及到[l,r]中比t大的数，且统一变为t，所以我们可以运用人类智慧，受到引入2的启发，我们可以考虑维护下面这些值

sum,maxi,sec,cnt

其中sum表示区间和，maxi表示区间最大值，sec表示区间严格次大值，cnt表示区间最大值的个数。当然还要维护tag。

区间最值操作的流程如下

设当前节点为p，管辖区间为[l,r]，操作区间为[L,R,t]

如果当前区间与[L,R]无交，直接return

如果当前区间不被[L,R]包含，继续递归

如果当前区间被[L,R]包含，再进行下列讨论

1.如果maxi\le t，那么询问无意义，直接return

2.如果sec<t<maxi，那么最大值会变为t，个数为cnt，并且打上tag

3.如果t\le sec，那么我们不知道修改的数个数为多少，所以继续递归

可以用势能分析法证明算法复杂度为O(n\log n)，具体见吉司机的论文。如果加上区间加，复杂度变为O(n\log^2 n)

3.注意事项

1.吉司机线段树经常细节很多，注意标记下传的顺序，以及在一些标记下传后，维护的数值会改变。

2.严格次大值，指严格小于最大值的值，而不是sort一边后的第二位，所以对于单个区间，其严格次大值初始化为-inf，并且注意次大值的更新。

3.某些题卡常，注意结构体线段树常数比数组小。

例题

线段树合并与分裂

线段树合并分裂的例题不太好找，这里只有少数几道

luoguP4556 雨天的尾巴

luoguP5494 线段树分裂

luoguP3224 永无乡

CF208E Blood Cousins

luoguP5384 雪松果树

吉司机线段树

luoguP6242 线段树3

luoguP4314 CPU监控

CF855F Nagini