线段树合并

适用条件:动态开点的(权值)线段树。

关于时间复杂度的结论:

  • 每次合并的代价是两棵树的公共节点数。
  • 若有n棵含有单个元素的树,经过n-1次merge操作,将他们合并成一棵树的代价是\(O(nlogn)\)或\(O(nlogC)\)的
  • 单次merge操作开销可大可小,均摊下一次就是一个log的。

关于空间复杂度,普通版本是\(O(nlogn)\)的,还不知道怎么优化。

直接给出代码,merge操作十分简洁:

 

题目

1.BZOJ 2212: [Poi2011]Tree Rotations

递归的给一颗二叉树,只有叶子有权值,对于每个非叶节点可以交换左右子树,使遍历后构成的序列逆序对最小。

对于一个子树,逆序对来自三部分,一个完全在左子树,一个完全在右子树,还有就是跨越左右子树的逆序对,可以发现交换左右子树的操作只会改变跨越部分的贡献,这里可以在线段树合并过程中求出逆序对的个数。

2.BZOJ 2733: [HNOI2012]永无乡

每个元素有点权,支持合并两个集合,查询一个集合内第k小的元素。

之前的做法是启发式合并+平衡树,每个元素最多插入\(O(logn)\)次,插入一次\(O(logn)\),所以总的时间复杂度\(O(nlog^{2}n)\)。

用线段树合并就可以做到\(O(nlogn)\)了,查询非常简单。

 

3.2018 南京网络赛 H set

首先这个题不是线段树,而是trie树,我们把每个数二进制从低位到高位插入trie,维护子树中插入的数的个数,合并类似线段树合并,修改操作比较巧妙,+1就相当于最低位+1,也就是最低位0变1,1变0,那么交换左右子树即可,进位的话就是进入(交换后)的左子树继续交换左右子树,递归下去。这样总的时间复杂度就是\(O(nlogC)\)。