题解 P3373 【【模板】线段树 2】

· · 题解

关于懒标记的理解

1.若节点node已经被标记过，不论乘还是加，则这个节点本身的sum值已经完成修改，但其子树所有的节点还没有修改

2.在查询时，由于有些节点的sum值还没有修改，因此要优先根据懒标记更新每一个node的子节点的sum值。即先完成更新，再查询，才能保证结果的正确性。

3.若某一节点node的add_tag有标记， 那么表示其子节点都需要进行对应的加法操作。那么如果此时进行区间乘法的更新，对于其子节点需要先乘其add_tag[son]， sum[son], mul_tag[son], 然后再加node节点的add_tag， 这样就完成了先加后乘的更新修改.满足乘法结合律。

4对于先乘后加操作也同理，如果node节点已经有了mul_tag，那么直接更新node的add_tag就可以了， 首先对于node满足之前的乘法没有影响本次加法， 其次对于node的子节点满足先乘之前的乘法， 再加本次加法， 所以也可以保证正确性

5 综上所述 push_down函数必须满足如下要求

//先乘
sum[node*2] *= mul_tag[node];
sum[node*2+1] *= mul_tag[node];

add_tag[node*2] *= mul_tag[node];
add_tag[node*2+1] *= mul_tag[node];

mul_tag[node*2] *= mul_tag[node];
mul_tag[node*2+1] *= mul_tag[node];

//再加
add_tag[node*2] += add_tag[node];
add_tag[node*2+1] += add_tag[node];

int mid = (l+r)/2;

sum[node*2] += add_tag[node] * (mid-l+1);
sum[node*2+1] += add_tag[node] * (r-mid);
//这里因为add_tag已经乘过了，所以代码实现实际上是分别乘完再加， 等价于先加完了一起乘

add_tag[node] = 0;
mul_tag[node] = 1;