懒标记法：

“区间修改”时，虽然把区间分成logn的结点，但是对于(tr[u].l>l&&tr[u].r<r)的结点，还是要把所有子节点全部修改一遍的，这样就会造成log(n)的复杂度。

如果，我们在修改的时候直接返回，只不过在回溯之前在当前结点p加一个标记，“该节点被修改但，子 节 点 未被更新”，则可以避免“徒劳的修改”，即本次修改并没有对后来的查询造成影响，从而减小时间复杂度。

注意，是子节点未被更新，自身保存的信息应该已经修改完毕。

要保证懒标记上的修改信息一定要适用于整个区间，如果区间的两部分一样，就要裂 开，分成两个子节点的标记。

在往后的的查询中，如果需要用到p结点，就把p结点的标记清空，并更新子节点的信息，同时为p的两个子节点增加标记。

这种从上到下的修改方式，被成为延迟标记，也成为懒标记。

1.pushup //用子节点修改父节点
2.pushdown //从上到下修改
3.build //建树
4.modify //修改
5.query //查询

一般情况下，pushdown放在modify和query的前部来保证add适用于整个区间，pushup放在build和modify的后部来更新父节点。

相关习题：
https://www.acwing.com/solution/content/24905/

扫描线法：