小结：线段树 & 主席树 & 树状数组

概要：

就是用来维护区间信息，然后各种秀智商游戏。

一定要注意标记的下放的顺序及影响！考虑是否有叠加或相互影响的可能！

和平衡树相同，在操作每一个节点时，必须保证祖先的tag已经完全下放。

size值的活用：主席树就是这样来的。支持区间加减，例题和模板：主席树

01（就是更新和不更新等这种对立操作）情况：我们就要在各个更新的操作中明白一件事，那就是总和不变。假设维护的是size，那么假设是标记下放，那么更新为(r-l+1)-size，例题：

pushdown的操作放在update、query等函数的位置不同影响很大，一般来说放在函数开头最保险（更新后边），原因是显然的（当遇到有冲突的区间更新时），比如说例题：

逆序建树：在一些题目中顺着的思路似乎想不通，那么就逆着想一想，想想前后顺序是否有关联，然后再操作，例题：

优化dp：对于一些dp中f(i)依赖于f(k), k<i的坐标型转移方程中，我们可以用线段树来维护这些区间信息，达到logn更新，例题：

树状数组的区间查询，目前还不会修改的。有两种更新区间方式（都是有序的），从左到右依次更新x、x+lowbit(x)、x+...+lowbit(...)，这种方法貌似常数大些。另一种是用x-lowbit(x)到x-1来更新x，例题：

树状数组区间维护和的话，例如[l, r]，那么先update(l, 1)，然后update(r+1, -1)，求和一样，这是为了能够修改的区间k大，例如

区间的合并：在一些题中，我们要维护某区间的连续性的长度时，我们可以维护两个值，L和R，分别表示从区间最左边和从区间最右边向另一边能延伸的长度，然后pushup的时候维护一下即可，例题：

然后就是看智商了。。

二维线段树：就是一颗树里边套了另一棵树。。

在写树上lca+主席树的时候维护的值不要搞错啊，就像这样，本来是id[u]的打成u。

离线区间后扫描：