概述
-
线段树分裂这里暂时没有。
-
线段树合并是指将管辖范围相同的两棵线段树对位(节点意义下)合并。
线段树合并
- 线段树合并支持各种统计子树的操作。
-
详细来讲就是,考虑某个题目给出一棵树(相对于普通线段树题目的数组而言,这里是每个树上点都对应着一个数组,不过父子之间数组差异往往较小),然后要询问某些子树中的结合性问题。
-
首先肯定有一种暴力做法就是对于每个子树都建一棵树。不过显然即使动态开点也会 \(MLE\),时间复杂度更不必谈了,建树远高于 \(n\log_2 n\)(因为大部分线段树要处理复数个数组)。
-
考虑利用树的性质:当前子树的结合性问题解=结合解(当前点,各个子树)。这种结合往往就是节点对位相结合,最多再维护一下。
-
所以我们先给每个点开一棵线段树(动态开点,不必真的开出来)。然后自上而下 dfs 一遍,先递归求解子树内的问题,然后将子树的线段树合并到当前节点上,最后回答当前子树的问题。
-
实现原理
离线线段树合并
-
合并后子树的线段树的信息丢失,必须离线问题,自下而上回答(当然实际操作是 dfs 递归求解)。优点是空间(合并时不会开新节点)。
-
先放代码,这也是典型的不看代码就是虚空讲解的算法。
il int merge(int now1,int now2,int l,int r){
if(!now1 || !now2) return now1|now2;
if(l==r){sum[now1]+=sum[now2]; return now1;}
ls[now1]=merge(ls[now1],ls[now2],l,mid);
rs[now1]=merge(rs[now1],rs[now2],mid+1,r);
pu(now1); return now1;
}
-
可以看到,这种合并的核心原理是如果都有就把第二棵的加到第一棵上,如果一方没有就直接模仿主席树进行连边(如果本来就是\(now1\)的子树就不用重新连边了)。
-
可见,一定不会新建节点,只有一方有的节点不会进入。纸面单次合并复杂度为 \(O(n_{both}\log_2 n_{both})\),即总共同节点数。
-
实际上,假设整棵树一共操作了 \(n\) 次(必须是单点修改,或者说每次修改至多开满一条独特链),那么将所有线段树合并成\(1\)个的总复杂度是大常数 \(O(n\log_2 m)\)。
-
这一结论可以通过势能分析给出:
-
合并开始前的 \(n\) 次操作每次至多开满一条链,线段树高 \(\log_2 m\),总复杂度 \(O(n\log_2 m)\)。
-
合并时,每个节点都至多被 dfs 到一次,因为假如两者都有某节点那其中某个节点就再也不用,只有一方有的节点根本没有进去(\(O(1)\) 连边可以算成它父亲节点的常数,不影响,毕竟线段树是二叉树)。既然总点数至多为 \(O(n\log_2 m)\),那么合并的总复杂度也就是大常数 \(O(n\log_2 m)\)。
-
在线线段树合并
-
模仿主席树,每次合并出的新树是一个新根,相加的点是新建的,只有一方的点是连边,然后以后再修改就和主席树一样。
-
从而子树的线段树信息不丢失,可以在线回答问题。
-
时间复杂度和上面基本一样(只有一方的点也是不进),但常数略大(开新点)。
-
空间复杂度等于时间复杂度(访问到的点数也就是新开的点数,最多三倍罢了)。我还没写过,写了会补上。
例题
P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并
- 维护区间最大数的 \(pos\)。
P3224 [HNOI2012]永无乡
- 不断进行合并,维护连通块(并查集)中的第 \(k\) 小。
线段树分裂
- 鉴于我现在不想写博客,我们只扔一下代码并说一下注意事项:
il void splitv(int now,int l,int r,int k,int &x){
x=newnode();
if(k<=mid){
a[x].rs=a[now].rs,a[now].rs=0;
if(l==r) return;
splitv(a[now].ls,l,mid,k,a[x].ls);
}
else{
a[now].ls=a[now].ls,a[x].ls=0;
if(l==r) return;
splitv(a[now].rs,mid+1,r,k,a[x].rs);
}
pu(now),pu(x); return;
}
-
这是一个按值域分裂的例子。有理由认为按数量分裂也是可以的。
-
在传统的 fhq 分裂中,我们会有
&x,&y
。但这里我们却钦定保留在 \(now\) 处,理由主要在于,如果把&x
置为 \(rt\) 一路操作过来的话,因为两者都取引用,故两者无法分成真正的两个东西(除非不让 \(y=now\))。故必须以这种方式实现。