线段树是基于分治思想的二叉树，用来维护区间信息。可以在 l o g n logn logn 的时间里执行区间修改和查询。

注：二叉树的空间要开 ( 4 × N ) (4\times N) (4×N)。

所谓线段树，就是叶子结点的值是输入的数组的值，而非叶子结点的值便是左儿子的值加上右儿子的值，例： ( 5 , 5 ) (5,5) (5,5) 和 ( 6 , 6 ) (6,6) (6,6) 的父结点是 ( 5 , 6 ) (5,6) (5,6)，值是 ( 5 , 5 ) s u m + ( 6 , 6 ) s u m (5,5)_{sum}+(6,6)_{sum} (5,5)sum​+(6,6)sum​。

设 l c lc lc 为 p < < 1 p tr[p].sum+=k; if(tr[p].l==x&&tr[p].r==x)return; int m=(tr[p].l+tr[p].r)>>1; if(xm)update(rc,x,k); } 3. 查找（find）:

核心：分割、拼凑

从根结点开始。

有三种情况：

需查找的范围覆盖了当前所在的范围，那就在答案中加上当前的值，并且返回。

需查找的范围位于当前范围的左侧，那就搜左儿子。

需查找的范围位于当前范围的右侧，那就搜右儿子。

最后输出拼凑所得的答案即可。

进行区间加数时，如果运用原版的那个，时间复杂度就是 O ( n ) O(n) O(n)，而这个加强版的时间复杂度成功维护在了 O ( l o g   n ) O(log\,n) O(logn)。那么优势就摆明了。

这个加强版用了懒惰标记（懒标记），那么懒标记是神马玩意？

懒标记相当于是过年时父母给小孩分零花钱，但小孩太多，分的话时间复杂度就废了，所以父母就说：“零花钱先放我这，要用的时候再发下去。”

这时，父结点就有了一个懒标记 a d d add add， a d d add add 的值就是父结点要给每个子结点的 值。

如图：

1~4 的区间要集体加 2，那就从根结点向下搜，若当前结点可以被目标区间完全覆盖，那就不再向下分配了，而是在此处打一个懒标记记录下面的结点要加的值即可。

如果没有完全覆盖，那就将要加的值向下分配，将当前懒标记清空。

新设一个函数为 pushdowm（简称pd）。用于向下分配。