树上差分 从抽象代数的角度讲，树上差分可以维护所有群上信息。 换句话说，满足结合律，存在「可减性」。 通过差分我们能将一个高纬问题以常数代价转化为低维问题，而问题低一维往往会简单非常多 —— lxl 太 $\textit{Trivial}$ 的我们就不提了。 下文成「前缀」为根到节点的路径。 luogu8201 [yLOI2021] 生活在树上（h…

树链剖分能够将一棵树按照某种法则剖分为若干条链，从而便于维护树上路径的信息。 按照剖出链的法则不同，其性质也不同，大体可将树剖分成重链剖分，长链剖分和用于 Link-Cut Tree 的剖分（实链剖分）。 其中重链剖分用途最广泛，本文也只介绍重链剖分。 重链剖分 定义与部分性质 给出如下定义 重儿子。对于一个非叶子节点，其重儿子为其以它的所有儿子为…