UOJ Logo itpublijojo的博客

博客

「主席树」和「可持久化线段树」有什么区别?

2024-04-25 14:46:36 By itpublijojo

如题

一直分不清楚,向dalao们求教!!!

评论

Cat_shao
结论:支持吉老师的观点——区别在于有没有西老师赐名。 可持久化线段树是我认为最标准、恰当的统一称呼。其他的都是别称或者俗称。 ------ 上面的回答有这么几种: - 二者是同一个东西。 - 主席树是可持久化线段树的真子集。 - 本质完全不同,或者不是子集。 我觉得 3 是最无力吐槽的,两句话反驳:对序列建线段树是线段树,对权值建线段树就不是线段树了?对序列修改可持久化是可持久化线段树,对权值修改可持久化就不是可持久化线段树了?1, 2 都有道理,因为“主席树”命名者本身就没有对其进行严格的定义,你说它是可持久化线段树的俗称(一个东西)也好,还是它仅指对“权值修改”可持久化的线段树也好(真子集),都是ok的。 转载自李煜东的回答https://www.zhihu.com/question/59195374/answer/400963467 请善用搜索引擎。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。