对于一类重链剖分问题的简单转换

Aegleseeker_ · 2024-12-21 18:35:48 · 算法·理论

有一些问题，比如 树上维护子树加，路径和 这类题目，大多数人都会直接写树剖。这里介绍一种码量远小于树剖的基于 dfs 序/欧拉序的单 \log 做法。

考虑搞出欧拉序，如果我们根据入、出栈给序列打上 1、-1 的标记，则不难发现 1 到 u 的路径和与欧拉序中 1 到 \operatorname{out}_u 的区间和是等价的。

同理，如果我们要单点修改，只需修改 \operatorname{in}_u 和 \operatorname{out}_u（一个加一个减）。

现在来考虑子树修改，不难发现是要对区间 [\operatorname{in}_u,\operatorname{out}_u] 做「正的权值加，负的权值减」。仔细想一下也很 simple，维护区间内 1 标记次数和 -1 标记次数，直接上下传标记即可。

总复杂度只有线段树的一个 \log，常数虽然有欧拉序的 2 倍和线段树 4 倍空间影响，但肯定比树剖优秀并且非常好写。

考虑如果是普通路径求和，直接利用树上差分的思想，求出 \operatorname{lca} 并多查几遍区间和即可。

如果倒过来变成 路径加，子树求和，也是可以实现的。读者不妨想一想如何沿用上述思想做到同样一只 \log。