做宠物网站赚钱吗,制作网页常用图片格式,上海市有哪些公司,专业网站建设费用怎么算定义
将树分割成若干条链#xff0c;以维护树上的信息#xff0c;若无特殊需求#xff0c;一般是重链剖分。
重链剖分 如何重链剖分 两个dfs
第一个dfs是预处理各个结点的基本信息#xff0c;第二个dfs是利用信息进行剖分#xff08;dfs序#xff09;
操作步骤
第一…定义
将树分割成若干条链以维护树上的信息若无特殊需求一般是重链剖分。
重链剖分 如何重链剖分 两个dfs
第一个dfs是预处理各个结点的基本信息第二个dfs是利用信息进行剖分dfs序
操作步骤
第一次dfs 更新当前结点信息子树个数、父结点信息、深度对子结点进行dfs子结点dfs之后把子结点的子树个数加到父结点更新重儿子。
第二次dfs
因为dfs序连续的值是一条链所以我们需要让树在进行dfs时优先对重儿子进行dfs之后再对其它轻儿子进行dfs 重链剖分的应用
将剖分的重链放在线段数组或者树状数组上然后在这个数据结构上进行维护。
对某条链上的节点进行更新
用数据结构对节点信息进行维护进行区间查询区间更新。
对某节点子树进行更新/查询
由dfs序可知某节点的入序和出序之间的连续数就是该节点的子树。
查询两节点的最近公共祖先LCA 操作步骤
当两节点不在同一条链上时选择深度更浅的结点跳到父链链首的父结点当两节点在同一条链上时深度更浅的点就是最近公共祖先LCA
查询、修改两节点之间路径的信息
主体还是寻找LCA就是如果跳到父链或是其它点把x到它首结点其它点之间结点信息进行更新。
