浅谈 线段树

概念和原理

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界

其实就是可以在O(nlogn)的时间复杂度内实现区间修改和区间查询

实现

• 首先定义某节点rt的左儿子节点编号为rt>>1,右儿子编号为rt>>1|1(即rt>>1+1)
• 再定义若此节点包含区间**[l,r],其左儿子包含区间[l,(l+r)>>1]**，右儿子包含区间 [(l+r)>>1+1,r]
• 最后定义根节点包含区间 [1,n]
  就可以得到类似下图的一棵树
  

用这种方式存好数组后，我们就可以开始对其进行区间修改和查询了
（由于单点修改和查询是区间修改和查询的子问题，故不再赘述）

区间修改

首先引入一个lazy标记的概念
lazy[i]指i号节点包含的区间被整体操作（加或减等）的累加值
比如说3号节点的区间被整体加上了5，lazy[3]=5
于是当我们要对一段区间进行整体操作修改时，不必将整个区间以O(n)的复杂度修改，只需要以O(1)的复杂度将其lazy标记维护好即可，若操作的区间不能够被某一个点完全覆盖，就将这个区间拆分成几个可以被某几个点所代表区间完全覆盖的区间，再进行操作

当然，维护好lazy标记的同时，我们也要维护好原来需要维护的值。比如说我们要维护区间和，那么当我们更新了某一区间的lazy后，我们就必须要用这个lazy标记来维护好区间和

void pushup(ll rt)//用更新后的子节点sum值更新自己的sum值
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(ll rt,ll len)//将节点rt的lazy标记向其子节点传递，更新子节点sum值
{
    if(!lazy[rt])return;
    lazy[rt<<1]+=lazy[rt];
    lazy[rt<<1|1]+=lazy[rt];
    sum[rt<<1]+=lazy[rt]*(len-((len)>>1));//understand?
    sum[rt<<1|1]+=lazy[rt]*(len>>1);
    lazy[rt]=0;
}
void add(ll l,ll r,ll nl,ll nr,ll rt,ll num)
{
    if(l<=nl&&nr<=r)
    {
        lazy[rt]+=num;
        sum[rt]+=(nr-nl+1)*num;
        return;
    }
    pushdown(rt,nr-nl+1);
    int m=(nl+nr)>>1;
    //若操作的区间不能够被某一个点完全覆盖，就将这个区间拆分成几个可以被某几个点所代表区间完全覆盖的区间
    if(m<r)add(l,r,m+1,nr,rt<<1|1,num);
    if(m>=l)add(l,r,nl,m,rt<<1,num);
    pushup(rt);
}

区间查询

留坑待补（做图累啊）