线段树的区间修改和懒标记

如果要求修改区间 \([l,r]\)，把所有包含在区间 \([l,r]\) 中的节点都遍历一次、修改一次，时间复杂度无法承受。我们这里要引入一个叫做 「懒惰标记」 的东西。

懒惰标记，简单来说，就是通过延迟对节点信息的更改，从而减少可能不必要的操作次数。每次执行修改时，我们通过打标记的方法表明该节点对应的区间在某一次操作中被更改，但不更新该节点的子节点的信息。实质性的修改则在下一次访问带有标记的节点时才进行。

仍然以最开始的图为例，我们将执行若干次给区间内的数加上一个值的操作。我们现在给每个节点增加一个 \(t_i\)，表示该节点带的标记值。

最开始时的情况是这样的

现在我们准备给 \([3,5]\) 上的每个数都加上 \(5\)。根据前面区间查询的经验，我们很快找到了两个极大区间 \([3,3]\) 和 \([4,5]\)（分别对应线段树上的 \(5\) 号点和 \(3\) 号点）。

我们直接在这两个节点上进行修改，并给它们打上标记：

我们发现，3
3 号节点的信息虽然被修改了（因为该区间管辖两个数，所以 𝑑3
d_3 加上的数是 5 ×2 =10
5 \times 2=10），但它的两个子节点却还没更新，仍然保留着修改之前的信息．不过不用担心，虽然修改目前还没进行，但当我们要查询这两个子节点的信息时，我们会利用标记修改这两个子节点的信息，使查询的结果依旧准确．

接下来我们查询一下 [4,4]
[4,4] 区间上各数字的和．

我们通过递归找到 [4,5]
[4,5] 区间，发现该区间并非我们的目标区间，且该区间上还存在标记．这时候就到标记下放的时间了．我们将该区间的两个子区间的信息更新，并清除该区间上的标记．

现在 \(6\)、\(7\) 两个节点的值变成了最新的值，查询的结果也是准确的。

void update(int l,int r,int c,int s,int t,int p){if(l<=s && t<=r){d[p]+=(t-s+1)*c,b[p]+=c;return;}int mid=s+((t-s)>>1);if(b[p]&&s!=t){d[p<<1]+=b[p]*(mid-s+1);d[(p<<1)+1]+=b[p]*(t-mid);b[p<<1]+=b[p];b[(p<<1)+1]+=b[p];b[p]=0;}if(l<=mid)update(l,r,c,s,mid,p<<1);if(r>mid)update(l,r,c,mid+1,t,(p<<1)+1);d[p]=d[p<<1]+d[(p<<1)+1];
}