差分 记录相邻节点值的差值。这样一来，前缀和就相当于原值了。 树上差分 树上差分基本上就是差分在树上的实现。因为差分的原理，我们先将所有点的权值改变成差分值，再更改一段区间内的所有值时，只需要更改首尾两端的值，如果要求值的话 dfs 重新加上前缀和就是正常的值了。 P3128 [USACO15DEC] Max Flow P 模板题，发现更改任意两点间的值只需要在两点差分值加...

点分治 点分治是一种树形分治的算法，它选择当前连通块一个重心，将树分成多个连通块进行处理，然后对每个连通块进行分治递归。 树的重心 树上的一个点，满足它的儿子的 \(size\) 的最大值最小。 可以证明，一个树有一个或者两个重心。若有两个重心，它俩一定是直接相连的。 处理问题 求树上给定路径联通的点的对数。我们发现将树分治后，形成了若干个连通块，而且这些连通块必定经过重心。...

P3384 【模板】重链剖分/树链剖分 适用问题 对一个给定的树，维护（修改、查询）其节点点权/边权，操作可 \(O(\log n)\) 次处理（如路径、子树）。 实现 将一棵树剖分成若干条链，每一条链通过区间数据结构维护。 将一个点的子树中最大的那个做为重儿子，其他的叫做轻儿子，对于所有点的重儿子连的链称为重链。我们将重链作为主链，将轻儿子构成的其他轻链加在重链的后面。很明显，...

笛卡尔树 笛卡尔树（Cartesian tree）是一种树形数据结构，每个节点都是一个区间，树的根节点表示整个区间，左儿子表示区间的左半部分，右儿子表示区间的右半部分。 笛卡尔树可以通过单调栈 \(O(n)\) 静态建造。 例题 P2659美丽的序列 题意 找出一个序列的所有子段中子段长度乘段内元素最小值的最大值。 思路 我们需要找出所有子段中贡献最大的，并且一个...