ix35_ 的博客

ix35_ 的博客

题解 P6012 【【模板】线段树分裂】

posted on 2020-01-26 15:56:45 | under 题解 |

线段树合并&分裂

网上找线段树合并/分裂的博客,讲得很清楚的也不多,某些部分只有自己 yy 一下了。

前置芝士:权值线段树,动态开点线段树。

在以下讨论中,我们设值域都为 $[1,n]$ 中的整数。

先定义代码中的一些东西:

$ch[i][0]$ 表示 $i$ 的左子结点, $ch[i][1]$ 表示 $i$ 的右子结点, $val[i]$ 表示 $i$ 点维护的值(出现了多少个该值域中的数)


一、线段树合并

有时我们需要整合两棵权值线段树的信息,这个整合的过程称为线段树合并。我们以最简单的合并为例:将两棵树相加。

两棵树如何相加呢?在权值线段树上,每个点维护了一个当前区间中数的个数,而数的个数是可以相加的,这个合并的过程可以理解为:把两个可重集合并,对应的权值线段树上发生的过程。而相加的原理很简单,两棵同构的线段树,只需要对应位置相加即可,如图:

注意动态开点线段树上某些点是缺的,其值当然是 $0$。

如何合并两棵线段树呢?

暴力是很简单的,我们枚举 $1$ 到 $n$,将第二棵树中对应位置上的值在第一棵树上做单点修改即可。

这个方法可以用启发式合并进一步优化,但只能适用于一些特殊情况(比如说如果带了分裂或者一个值在多棵树上出现,启发式合并就歇菜了)。


而我们可以递归处理线段树合并,设我们现在要合并的是以 $x,y$ 为根的两棵子树,要确保它们在线段树上处于同一位置(即它们是两棵树上代表同一区间的点)。

如果 $x,y$ 其中一个为 $0$ (也就是某个权值线段树上没有这个位置的点),无需合并,返回另一个非 $0$ 的点即可。

否则,我们先合并 $x,y$ 的左右子结点,再根据两子结点的信息整合得到 $x,y$ 合并的结果。

线段树合并一般有两种写法:新建结点和不新建结点。但是两者原理是一样的。

新建结点的写法:

新建一个结点 $p$ 作为 $x,y$ 合并的结果。将 $ch[x][0]$ 和 $ch[y][0]$ 的合并结果记为 $sl$, $ch[x][1]$ 和 $ch[y][1]$ 的合并结果记为 $sr$,令 $sl,sr$ 分别为 $p$ 的两个子结点,对 $p$ 做一次 pushup​ 即可得到结果。此后 $x,y$ 就没有用的,可以回收(节省空间的方法)。但是有时 $x,y$ 的信息不能丢,这时就不能回收。

int merge (int x,int y,int l,int r) {
    if (!x||!y) {return x+y;}    // 只有一边有点,不用合并
    int mid=(l+r)>>1,p=newnod(); // 创建一个新结点 p
    if (l==r) {                  // 边界(某些时候可以省略,见下面一个代码)
        val[p]=val[x]+val[y];
        return p;
    }
    int sl=merge(ch[x][0],ch[y][0],l,mid),sr=merge(ch[x][1],ch[y][1],mid+1,r);
    ch[p][0]=sl,ch[p][1]=sr;
    recyc(x),recyc(y);           // 垃圾回收(我有时写 recyc,有时写 del,是一个东西,这个函数见最后的本题代码)
    upd(p);                      // pushup
    return p;
}

不新建结点的写法:

如果一个点合并完就可以扔掉,那还可以写得更加简便,直接将 $x$ 作为合并后的结果,将 $y$ 的值加到 $x$ 上即可(直接对应位置相加),甚至不需要 pushup,但是注意,如果 $x=0$,返回的是 $y$,所以比较保险的写法是 $x=merge(x,y)$。

事实上这里我们连当前区间的左右端点 $l,r$ 也可以去掉,因为到叶结点后 $ch[x][i]$ 自然是 $0$,自然会返回。

int merge (int x,int y) {
    if (!x||!y) {return x+y;}     // 只有一边有点,不用合并
    val[x]+=val[y];               // 信息整合
    ch[x][0]=merge(ch[x][0],ch[y][0]);
    ch[x][1]=merge(ch[x][1],ch[y][1]);
    del(y);                       // 垃圾回收
    return x;
}

这东西看着很一般,复杂度怎么样呢?

单独讨论一次合并的复杂度没有什么意义,如果两棵树都是满的,复杂度就到 $O(n)$ 了,所以一般从均摊角度来讨论。


如果现在有 $m$ 棵线段树(每棵树初始只有一个位置有权值),经过若干次合并最后变成 $1$ 棵,此过程的复杂度是多少呢?

例题:P4556P5298

不说具体怎么做了,这些题都有很完整的题解,我就分析一下复杂度(这些题都符合上面提到的模型)。

一开始有 $m$ 棵树,只有一个位置有权值,所以一棵树上结点数量为 $O(\log n)$, $m$ 棵树的结点总数也就是 $O(m\log n)$。

分析上面的代码,发现每一次进入 merge 函数,要么停止递归,要么继续递归并有一个点被垃圾回收。显然停止递归的 merge 次数与继续递归的 merge 次数同阶(不继续递归的情况是从递归的情况出来的,不会超过其两倍的数量)。

因此整个过程的复杂度就等于继续递归的 merge 函数进入次数的复杂度(每一次执行 merge 在不考虑递归时复杂度 $O(1)$),也就等同于被删除的结点个数,是不超过 $O(m\log n)$ 的(有点像势能分析?)。

注意复杂度本身和是否回收结点没有关系,只是借以分析而已。

所以整个过程的复杂度也就是 $O(m\log n)$。

但是线段树合并的复杂度不总是对的,不过本题中 $1$ 操作的复杂度我不知道是否是均摊 $\log n$ 的,希望有人能证明/证伪一下。


二、线段树分裂

将一个可重集前 $k$ 小的数与之后的数分成两个集合,那么对应的权值线段树就要裂成两棵权值线段树。

举个栗子:将 $[1,3]$ 和 $[4,4]$ 分开(这里为了方便直接用权值描述了,一般是按照第 $k$ 小的位置来的):

暴力当然也很简单,找到第 $k$,后面的值新建一棵树,在原树上减掉即可。

然而我们可以仿照 FHQ Treap 的套路,实现 $O(\log n)$ 的分裂。

设我们现在要将以 $x$ 为根的树分裂成 $x,y$ 为根的这两棵树( $y$ 本来是不存在的,传引用),以第 $k$ 小为界,前 $k$ 小在 $x$,之后的在 $y$。

首先看 $x$ 的左子树的值 $v$,如果 $v<k$,那么左侧依然归 $x$(不需要处理),递归右侧即可,注意 $k$ 变成了 $k-v$。

如果 $v=k$,那么左边归 $x$,右边归 $y$ 即可。

如果 $v>k$,那么右边归 $y$,递归左侧即可。

看完结构后看权值, $x$ 的新权值当然是 $k$,那么 $y$ 的权值也就是 $x$ 原先的权值减去 $k$ 了。

可以发现,如果 $v\ge k$,那么 $y$ 的右子结点都是需要赋值的,下面的代码直接归到了同一句里(else 所在的那一句):

void split (int x,int &y,ll k) {
    y=newnod();
    ll v=val[ch[x][0]];
    if (k>v) {split(ch[x][1],ch[y][1],k-v);}
    else {swap(ch[x][1],ch[y][1]);}         // 右子树归 y,x 的右子树变成 0
    if (k<v) {split(ch[x][0],ch[y][0],k);}
    val[y]=val[x]-k;
    val[x]=k;
    return;
}

这个每次只递归一边,复杂度是 $O(\log n)$ 没啥问题。


三、这道题

每个操作分别来看。

将 $[x,y]$ 分裂出来:先分出 $[1,x-1]$,再从 $[x,n]$ 中分出 $[x,y]$ 和 $[y+1,n]$,最后把 $[1,x-1]$ 和 $[y+1,n]$ 合并。我注意到 std 不是这样的,std 的分裂写的就是分裂出一个区间,我在这里用了一次合并,但是复杂度是对的,稍后会证明复杂度为 $O(\log n)$;

将 $t$ 树合并入 $p$ 树:单次合并即可,不确定复杂度,但是不超过 $2\times 10^3$ 次总没问题的;

$p$ 树中插入 $a$ 个 $q$:单点修改,复杂度 $O(\log n)$;

查询 $[x,y]$ 中数的个数:区间求和,复杂度 $O(\log n)$;

查询第 $k$ 小:经典操作,复杂度 $O(\log n)$。

最后说一下 $0$ 操作的复杂度:

两次分裂是 $O(\log n)$ 没问题,主要看合并。注意合并的两个区间没有交集,我们就看一看每一层会涉及几个点。

对于第 $1$ 层:总共就 $1$ 个点...

对于第 $i$ 层:如果第 $i-1$ 层只递归下来 $1$ 个点(设为 $u$),再设 $x$ 和 $y$ 为 $u$ 的左右子结点。如果前一棵树占了 $x,y$ 两个点,那么因为后一棵树占的区间严格在前一棵树之后,所以只会占 $y$,那么需要递归的只有 $y$,反过来的话同理需要递归的只有 $x$,所以第 $i$ 层也只需要递归 $1$ 个点。

每一层只往下递归一个点,复杂度就是 $O(\log n)$ 了。

代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=200010;
int n,m,tot,cnt,seq=1,op,x,y,z,bac[MAXN<<5],ch[MAXN<<5][2],rt[MAXN];
ll val[MAXN<<5];
int newnod () {return (cnt?bac[cnt--]:++tot);}
void del (int p) {
    bac[++cnt]=p,ch[p][0]=ch[p][1]=val[p]=0;
    return;
}
void modify (int &p,int l,int r,int pos,int v) {
    if (!p) {p=newnod();}
    val[p]+=v;
    if (l==r) {return;}
    int mid=(l+r)>>1;
    if (pos<=mid) {modify(ch[p][0],l,mid,pos,v);}
    else {modify(ch[p][1],mid+1,r,pos,v);}
    return;
}
ll query (int p,int l,int r,int xl,int xr) {
    if (xr<l||r<xl) {return 0;}
    if (xl<=l&&r<=xr) {return val[p];}
    int mid=(l+r)>>1;
    return query(ch[p][0],l,mid,xl,xr)+query(ch[p][1],mid+1,r,xl,xr);
}
int kth (int p,int l,int r,int k) {
    if (l==r) {return l;}
    int mid=(l+r)>>1;
    if (val[ch[p][0]]>=k) {return kth(ch[p][0],l,mid,k);}
    else {return kth(ch[p][1],mid+1,r,k-val[ch[p][0]]);}
}
int merge (int x,int y) {
    if (!x||!y) {return x+y;}
    val[x]+=val[y];
    ch[x][0]=merge(ch[x][0],ch[y][0]);
    ch[x][1]=merge(ch[x][1],ch[y][1]);
    del(y); 
    return x;
}
void split (int x,int &y,ll k) {
    if (x==0) {return;}
    y=newnod();
    ll v=val[ch[x][0]];
    if (k>v) {split(ch[x][1],ch[y][1],k-v);}
    else {swap(ch[x][1],ch[y][1]);}
    if (k<v) {split(ch[x][0],ch[y][0],k);}
    val[y]=val[x]-k;
    val[x]=k;
    return;
}
int main () {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) {
        scanf("%d",&x);
        modify(rt[1],1,n,i,x);
    }
    for (int i=1;i<=m;i++) {
        scanf("%d",&op);
        if (op==0) {
            scanf("%d%d%d",&x,&y,&z);
            ll k1=query(rt[x],1,n,1,z),k2=query(rt[x],1,n,y,z);
            int tmp=0;
            split(rt[x],rt[++seq],k1-k2);
            split(rt[seq],tmp,k2);
            rt[x]=merge(rt[x],tmp);
        } else if (op==1) {
            scanf("%d%d",&x,&y);
            rt[x]=merge(rt[x],rt[y]);
        } else if (op==2) {
            scanf("%d%d%d",&x,&y,&z);
            modify(rt[x],1,n,z,y);
        } else if (op==3) {
            scanf("%d%d%d",&x,&y,&z);
            printf("%lld\n",query(rt[x],1,n,y,z));
        } else if (op==4) {
            scanf("%d%d",&x,&y);
            if (val[rt[x]]<y) {printf("-1\n");continue;}
            printf("%d\n",kth(rt[x],1,n,y));
        }
    }
    return 0;
}