【8】树链剖分 学习笔记

引入树链剖分顾名思义就是将一棵树剖成一条条链。这种算法可以帮助我们快速解决一类和树上路径有关的的问题。P3384 【模板】重链剖分 / 树链剖分给定一棵n nn个点的树需要支持q qq次询问分为如下几种1 x y z表示将树从x xx到y yy结点最短路径上所有节点的值都加上z zz。2 x y表示求树从x xx到y yy结点最短路径上所有节点的值之和。3 x z表示将以x xx为根节点的子树内所有节点值都加上z zz。4 x表示求以x xx为根节点的子树内所有节点值之和。n , q ≤ 10 5 n,q \le 10^5n,q≤105。算法流程既然知道了需要剖那么怎么剖以及剖好之后如何解决问题下面我们详细说说。怎么剖首先看怎么剖。树剖有两种一种是重链剖分一种是长链剖分后者用的比较少这里我们讲前面这种。对于树上每个点我们记录其重儿子为其所有儿子中子树大小最大的那一个重边为其连向重儿子的边。其余的则反过来称为轻儿子和轻边。例如下图中的树每个点旁边用蓝笔写出了其重儿子叉表示该点是叶子没有儿子。像5 55这种有多个最大子树的可以任选一个作为重儿子。绿色的边就是重边。像这种多个重边连起来的如1 → 2 1 \to 21→22 → 5 2 \to 52→55 → 7 5 \to 75→7当然单个重边也是可以的一条链就叫做重链这条链最上面一个点此处为1 11就叫做该链的链头。对于一棵树上的任意一个点我们有性质一个点最多向上跳O ( log ⁡ n ) O(\log n)O(logn)条重链就会跳到根。理解一下这个性质。首先啥叫“跳”啊跳就是每一次跳到当前所在重链的链头的父亲。如果一个点到其父亲的边不是重边呢这里可以把这个点看作一个包含0 00个重边的重链跳到其父亲即可。为啥只会跳O ( log ⁡ n ) O(\log n)O(logn)次感性理解一下每次跳过一条重链为了满足重链的性质也就是重儿子的性质其子树比其它子树都要大可能的整个树的大小就要翻倍。所以这里只会跳O ( log ⁡ n ) O(\log n)O(logn)次。这些信息都可以用一次 DFS 求出。这样就完成了我们的剖分过程下面我们来看看这个有什么用。如何用来回到例题看看树剖咋用。首先我们基本就不会啥树上的数据结构考虑把这棵树拍平到序列上这样我们的操作就比较好进行了。咋拍呢我们也没学过啥别的啊就直接用 DFS 序吧。但是这样我们重链的优秀性质就没了——那怎么行我们想到一个折中方案DFS 的时候如果该点不是叶子那么先遍历重儿子。这样一条重链上的点的 DFS 序就是连续的了。看起来问题差不多解决了因为子树修和子树和都可以用 DFS 序拍成区间加和区间求和。链也可以因为有性质我们直接一直向上跳就可以了。但是我们怎么知道跳到哪里是 LCA 呢如果 LCA 在一个重链中间怎么办这里有一个解决办法我们每次选链头深度大的那边跳上去直到x xx和y yy在同一条重链上。因为 LCA 这个点至少有一个轻儿子否则x xx和y yy就已经在一条重链了这里可以自行思考所以总有一个点会正好跳到 LCA 上面。当跳到一条重链上面的时候此时一个点是 LCA另一个点一定是其后代此时这两个点之间的链也一定在原来的x → y x \to yx→y路径上而且 DFS 序也是连续的。这就意味着我们可以将一条链拆成序列上的O ( log ⁡ n ) O(\log n)O(logn)个连续区间然后就可以直接线段树啦~线段树就是区间加区间求和就可以了。分析一下复杂度空间上没啥特别的就是O ( n ) O(n)O(n)。时间上我们在跳重链的时候要跳O ( log ⁡ n ) O(\log n)O(logn)次每次要花O ( log ⁡ n ) O(\log n)O(logn)的时间更新所以总时间复杂度是O ( n log ⁡ 2 n ) O(n \log^2 n)O(nlog2n)。代码比较好写。:::info[Code]{open}#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN1e55;inta[N],dfnid;vectorinte[N];intsiz[N],son[N],dep[N],fa[N],dfn[N],top[N],d[N];structsegtree{inttree[4*N],tag[4*N];voidpushup(intx){tree[x]tree[x*2]tree[x*21];}voidpushdown(intx,intl,intr){intmid(lr)1;tree[x*2](mid-l1)*tag[x];tree[x*21](r-mid)*tag[x];tag[x*2]tag[x];tag[x*21]tag[x];tag[x]0;}voidbuild(intx,intl,intr){if(lr)returntree[x]a[d[l]],tag[x]0,void();intmid(lr)1;build(x*2,l,mid);build(x*21,mid1,r);pushup(x);}voidupdate(intx,intl,intr,intL,intR,intd){if(Rl||Lr)return;if(LlrR)returntree[x](r-l1)*d,tag[x]d,void();pushdown(x,l,r);intmid(lr)1;update(x*2,l,mid,L,R,d);update(x*21,mid1,r,L,R,d);pushup(x);}intquery(intx,intl,intr,intL,intR){if(Rl||Lr)return0;if(LlrR)returntree[x];pushdown(x,l,r);intmid(lr)1;returnquery(x*2,l,mid,L,R)query(x*21,mid1,r,L,R);}}tr;voiddfs1(intnow,intf){fa[now]f;dep[now]dep[f]1;siz[now]1;intmxsz0,mxid0;for(autox:e[now]){if(xf)continue;dfs1(x,now);siz[now]siz[x];if(siz[x]mxsz)mxszsiz[x],mxidx;}son[now]mxid;}voiddfs2(intnow,intf,intrt){dfn[now]dfnid;top[now]rt;if(son[now])dfs2(son[now],now,rt);for(autox:e[now]){if(xf||xson[now])continue;dfs2(x,now,x);}}signedmain(){intn,m,r,p;cinnmrp;for(inti1;in;i)cina[i];for(inti1,u,v;in;i)cinuv,e[u].push_back(v),e[v].push_back(u);dfs1(r,0);dfs2(r,0,r);for(inti1;in;i)d[dfn[i]]i;tr.build(1,1,n);while(m--){intopt,x,y,z;cinoptx;if(opt1){cinyz;while(top[x]!top[y]){if(dep[top[x]]dep[top[y]])swap(x,y);tr.update(1,1,n,dfn[top[y]],dfn[y],z);yfa[top[y]];}if(dep[x]dep[y])swap(x,y);tr.update(1,1,n,dfn[x],dfn[y],z);}elseif(opt2){ciny;intsum0;while(top[x]!top[y]){if(dep[top[x]]dep[top[y]])swap(x,y);sumtr.query(1,1,n,dfn[top[y]],dfn[y]);yfa[top[y]];}if(dep[x]dep[y])swap(x,y);sumtr.query(1,1,n,dfn[x],dfn[y]);coutsum%pendl;}elseif(opt3){cinz;tr.update(1,1,n,dfn[x],dfn[x]siz[x]-1,z);}else{couttr.query(1,1,n,dfn[x],dfn[x]siz[x]-1)%pendl;}}return0;}:::练习题 1P3178 [HAOI2015] 树上操作P3833 [SHOI2012] 魔法树P2590 [ZJOI2008] 树的统计P2146 [NOI2015] 软件包管理器这些题目只需稍微转换一下题意或改一下线段树即可。边权转点权有些题需要我们维护的是边权而不是点权怎么办呢P4315 月下“毛景树”给定一棵树进行如下几种操作Change k w将第k kk条树枝上毛毛果的个数改变为w ww个。Cover u v w将节点u uu与节点v vv之间的树枝上毛毛果的个数都改变为w ww个。Add u v w将节点u uu与节点v vv之间的树枝上毛毛果的个数都增加w ww个。Max u v询问节点u uu与节点v vv之间树枝上毛毛果个数最多有多少个。n , q ≤ 10 5 n,q \le 10^5n,q≤105。边权直接处理起来挺麻烦的能不能想个办法转成点权呢当然可以我们让每个边里深度较大的那个点作为“代表”把边权换成这个点的点权就好了。修改和查询的时候需要注意不要把 LCA 也改了因为 LCA 存的是它上面那条边所以最后一次更新的时候从 LCA 的儿子开始即可。练习题 2P1505 [国家集训队] 旅游P2680 [NOIP 2015 提高组] 运输计划总结 后记树链剖分是一种很常用的算法可以和很多其他数据结构结合灵活使用。这篇主要是基础内容后面如果需要可能会更进阶 qaq。码字不易能否给个赞 /wq 若对文章有任何问题和建议可以与作者私信交流。