有些时候,我们需要合并两棵动态开点线段树维护的信息,而一个个枚举插入又太慢了,这时就需要线段树合并的技巧。
假设现在要合并下图中蓝色的线段树和红色的线段树:

朴素的做法是一个一个叶节点插入,但是考虑同时在这两棵树上面 dfs:

两棵树的当前位置都有节点,所以继续往下递归:

两棵树的当前位置都有节点,继续往下递归:

发现蓝色线段树当前位置没有节点了,所以可以直接把红色线段树当前位置的节点拿来用,并回溯:

发现当前位置还没有递归处理完,往右递归:

发现红色线段树当前位置没有节点了,所以可以直接把蓝色线段树当前位置的节点拿来用,并回溯:

当前位置递归处理完了,新建一个节点来保存子树信息,并回溯:

发现当前位置还没有递归处理完,往右递归:

发现蓝色线段树当前位置没有节点了,所以可以直接把红色线段树当前位置的节点拿来用,并回溯:

当前位置递归处理完了,新建一个节点来保存子树信息,并回溯:

这样就完成了合并。
总结一下合并的规则:
-
同时在这两棵线段树上面 dfs;
-
若当前位置是叶节点,新建一个节点保存合并的信息,并回溯;
-
若两棵树的当前位置都有节点,继续往下递归;
-
若有一棵树当前位置没有节点了,直接把另一棵树当前位置的节点拿来用,并回溯;
-
当前位置递归处理完后,新建一个节点来保存子树信息,并回溯。
其中除了第二条,其它在图示里面都见过。第二条也很好理解,因为叶节点无需也没法继续递归下去。
将共有 个叶子节点的任意多棵线段树以任意顺序合并的时间复杂度是 的。证明如下:
不难发现,每次 dfs 合并两个节点可以看成丢掉一个节点,由于总共只有 个节点,所以时间复杂度就是 的。
具体代码实现如下:
struct node
{
int lson,rson;
int val;
}tree[500005];
int cnt; // 节点数量(用于动态开点)
int meg(int x,int y)
{
if(x==0||y==0) return x+y;
if(tree[x].lson==0&&tree[x].rson==0)
{
int res=++cnt;
tree[res]=tree[x];
tree[res].val+=tree[y].val;
return res;
}
else
{
int res=++cnt;
tree[res].lson=meg(tree[x].lson,tree[y].lson);
tree[res].rson=meg(tree[x].rson,tree[y].rson);
upd(res);
return res;
}
}
有些时候空间卡得紧,我们在合并的时候可以不新建节点,代价是破坏某棵线段树的结构:
struct node
{
int lson,rson;
int val;
}tree[500005];
int cnt; // 节点数量(用于动态开点)
int meg(int x,int y)
{
if(x==0||y==0) return x+y;
if(tree[x].lson==0&&tree[x].rson==0)
{
tree[x].val+=tree[y].val;
return x;
}
else
{
tree[x].lson=meg(tree[x].lson,tree[y].lson);
tree[x].rson=meg(tree[x].rson,tree[y].rson);
upd(x);
return x;
}
}