社区讨论

求问,可撤销线段树

学术版参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mhjsdbuw
此快照首次捕获于
2025/11/04 07:43
4 个月前
此快照最后确认于
2025/11/04 07:43
4 个月前
查看原帖
对于线段树,任何操作均可支持栈序撤销。只是想询问如何做到更优秀的空间复杂度。
当修改存在逆元时,空间复杂度为 O(q)O(q)
当修改不存在逆元时,比如一种支持区间覆盖,且必须 pushdown 的线段树,请问能做到什么空间复杂度。
目前我能够做到 4qlogn4q\log n

回复

4 条回复,欢迎继续交流。

正在加载回复...