@[yiming564](/user/554746) 带均摊的数据结构无法持久化
by piggy123 @ 2024-02-24 21:08:59
@[piggy123](/user/380042) 大佬可以解释的详细一点吗，我不是很理解
by yiming564 @ 2024-02-24 22:02:20
@[yiming564](/user/554746) 就是说这个路径压缩复杂度是均摊的一个 $\log$，那么最坏情况下一次操作复杂度可以高于这个。
然后我如果可持久化就一直对着这个复杂度最高的搞，就似了
by int08 @ 2024-03-19 17:40:18
呃呃，其实很好理解。
首先是从内存上来说，一次单点修改是 $O(\lg N)$，查询时的一次路径压缩可不仅仅只有一次单点修改。
其次从时间复杂度来说，任何均摊的时间数据结构都做不到可持久化。比如 splay 就是依靠出名的 `splay` 操作来将 $O(N)$ 的链变得优美。那么可持久化后，假如我不在现在的版本做修改，而专挑那条链改，那就仁者见仁，智者见智了 ┑(￣Д ￣)┍。类似的，这里也一样，专挑还没压缩的版本死命改，也是一样的 awa
by _venti @ 2024-04-23 13:09:32