关于dsu on tree 和 线段树合并

学术版

ka_da_Duck @ 2025-01-11 11:15:16

我发现大部分题目都能用线段树合并做，但是dsu on tree 在小部分题目中貌似能够优化时间和空间复杂度。

想请教下dsu on tree 有什么优势，或者哪些情况下不能用线段树合并代替它呢？

by 缪凌锴_Mathew @ 2025-01-11 11:20:42

如果你说的是静态链分治，时间多一只 \log，空间少一只 \log。

by hytallenxu @ 2025-01-11 11:22:35

@ka_da_Duck 回答第一个问题，dsu on tree 的优势是难度低，大部分都是板子题，思维转换不需要太大技巧。同时，相较于线段树合并的常数更低（某些 dsu on tree 的 \Theta(n \log^2 n) 与线段树合并的 \Theta(n \log n) 速度相当）。但是 dsu on tree 的使用范围有限吧。

by ka_da_Duck @ 2025-01-11 11:34:02

@缪凌锴_Mathew@hytallenxu 感谢大佬！

by 5k_sync_closer @ 2025-01-11 12:12:37

@ka_da_Duck dsu on tree 不能可持久化，很多维护 SAM 的 endpos 的题不能用 dsu on tree

by litjohn @ 2025-01-11 14:33:59

@hytallenxu 我想不通，线段树的点数不是O(n)的吗？那么合并不也应该是O(n)的吗？

by hytallenxu @ 2025-01-11 15:05:59

@litjohn 额请您左转 OI-WIKI，我们通常来说合并是只合并根到叶子路径上的，深度是 \log n，所以每次是 \Theta(\log n)。

|