树链剖分（本文仅介绍 重链剖分（Heavy-Light Decomposition））的用途： 更新树上两点之间的路径上的所有点的值 求树上两点之间的路径上的最大值、最小值、和（或任意满足结合律的运算） 思想 树链剖分即把整棵树剖分成若干条链，然后用线段树等数据结构来维护链上的信息。重链剖分可以将树上的任何一条路径划分成不超过 $O(\log n)$ 条连续的链。 定义： 重子节点 表示其子节点中…
树链剖分（本文仅介绍 重链剖分（Heavy-Light Decomposition））的用途： 更新树上两点之间的路径上的所有点的值 求树上两点之间的路径上的最大值、最小值、和（或任意满足结合律的运算） 思想 树链剖分即把整棵树剖分成若干条链，然后用线段树等数据结构来维护链上的信息。重链剖分可以将树上的任何一条路径划分成不超过 $O(\log n)$ 条连续的链。 定义： 重子节点 表示其子节点中…
讨论
登录后参与讨论
还没有评论，来说第一句吧。