关于可持久化线段树区间修改
查看原帖
关于可持久化线段树区间修改
577796
prokali楼主2023/10/18 08:20

RT,本人先用了标记下传的方法,然后过了之后去看题解,结果发现清一色的标记永久化,再根据这个帖子中@ Libingyue2011的说法,标记下传空间复杂度可以卡到 O(nm)O(nm) ,但是个人认为每次访问可持久化线段树时最多有log2(n)log_2(n) 级别的节点标记下传,新建节点数也是这个级别的,因此空间复杂度应该是 O(mlog2(n))O(mlog_2(n)) 级别的,求大佬解答。

2023/10/18 08:20
加载中...