维护树上问题时，我们希望能将一条链/一个子树上的点 映射 到 连续 的位置，即区间上，这样就可以用区间数据结构来维护此类信息了。
重链剖分提供了一种映射的方式，即对树上的点重标号，树上一条路径上的点映射为 \(O(\log n)\) 个区间（此处默认 \(\{1,2\}\) 两个点构成 \([1, 3)\) 这个区间，下同），一个点的子树映射为 \(1\) 个区间。
具体的映射方法见 OI Wiki，此处仅写出它的思想
重链剖分 学习笔记
发布时间 2023-07-04 17:49:12作者: 383494