tree - Segment树的延迟更新

Question

我有一个问题，需要一个可以处理 2 个操作的结构：

1. 将节点的值从位置 x 更改为位置 y 到 newValue。

2. 获取从位置 a 到 b 的值的总和。

节点数为 50000，查询数为 50000。我试图用延迟更新实现 IT 树，但我不知道如何。第一个操作与通常的加法和乘法操作有些不同。

Answer 1

对于范围 [l...r] 的给定节点，存储范围和相应范围的惰性值的总和。使用惰性值 = -1 的初始值构建段树。

对于更新操作，使用正常方法继续使用段树。在特定节点，使用惰性值更新节点的总和，并更新子节点的惰性值。当范围与节点完全重叠时，更新该节点的 sum 值，并将其子节点的惰性更新为当前值。

对于查询操作，使用正常方法继续使用段树。在特定节点，使用惰性值更新节点的总和，并更新子节点的惰性值。然后如果范围与节点重叠，则返回该节点的总和值。