线段树能否同时支持区间加、区间求和与区并？

喵仔牛奶 @ 2023-07-15 09:22:01

by 喵仔牛奶 @ 2023-07-15 09:24:13

线段树能否同时支持区间加、区间求和与合并？

by Killer_joke @ 2023-07-15 09:31:23

@喵仔牛奶 您的区间合并指的是什么。

by SevenElevenThirteen @ 2023-07-15 09:31:43

啥是“区间合并”？具体怎么合并

by 喵仔牛奶 @ 2023-07-15 09:37:01

@Killer_joke @yhk1001 指线段树合并（不是区间）

by kyEEcccccc @ 2023-07-15 09:49:59

@喵仔牛奶 可以。线段树合并时，不下传 tag，直接合并 tag 即可。

by kyEEcccccc @ 2023-07-15 09:53:34

可以不下传 tag 的条件是操作具有交换律，例如区间加标记。

by 蒟酱 @ 2023-07-15 09:56:30

合并 tag 即可，复杂度显然正确

by yllcm @ 2023-07-15 10:20:59

@喵仔牛奶 x 子树与 y 子树合并的时候如果 y 节点一个儿子都没有的话就直接在 x 节点上打标记，x 一个儿子都没有同理，否则 x 节点和 y 节点新建儿子并下传标记，复杂度是正确的

by yllcm @ 2023-07-15 10:21:46

复杂度证明考虑定义势能为总节点个数+只有一个儿子的节点个数，容易发现一次操作势能至少减少 1。

by 喵仔牛奶 @ 2023-07-15 10:22:39

thx