线段树合并复杂度证明

前言

近期对线段树合并有了更深的了解，所以在这里写一下一些自己的想法

适用问题

线段树合并有一类经典的模板，现在对于一棵有n个叶子节点的树（Tip:对于一棵$n$个叶子节点的树，其节点数量小于等于$2n$，特殊的，我们把只有一个儿子一个父亲的点都先删除），每个叶子节点上都有一个值域为m的值在线段树中，一个非叶子节点节点的线段树由所有子节点的线段树合并而成，求相关的信息

代码

inline node*merge(node*x,node*y)//node为线段树节点的结构体名称
{if(x==NULL&&y==NULL)return NULL;//这一句在这里可能不重要，但当下面两个if里有其它操作的时候就需要加if(x==NULL)return y;//NULL说明该指针为空if(y==NULL)return x;x->lson=merge(x->lson,y->lson);x->rson=merge(x->rson,y->rson);return x;
}

复杂度

对于整棵树，做完的复杂度为$O(nlogm+N)$
证明：
由于要遍历整棵树，所以有至少的O(N)的复杂度
对于一个叶子节点，其构树的复杂度为$O(logm)$。容易发现，两棵线段树合并时，由于如果一棵线段树为空就不做，只有两颗线段树都有值时往下，所以往下dfs的终止节点一定是两棵线段树节点的lca。对于一个节点，做完其子树的线段树合并的复杂度为∑i为线段树上两个叶子节点的lcadepth[i]\sum_{i为线段树上两个叶子节点的lca}depth[i]i为线段树上两个叶子节点的lca∑​depth[i]
（Tip：由于对于两条路径可能会有相交之处，所以这个复杂度是上界，实际上这部分是不满的）
每有一个满足条件的lca，说明有两个值合并在一起了，合并次数为N-1次，而深度是$O(logm)$的，所以总复杂度为O(nlogm+N)
证毕

例题

[PKUWC2018][loj2537]Minimax

总结

这是一个很妙的模型，乍一眼复杂度不容易得出，而且比较好写，值得记住

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！