线段树学习笔记

已知一个数列，你需要进行下面两种操作

1.将某区间每一个数加上x

2.求出某区间每一个数的和

线段树，即是将一个整区间分解成几小区间，保存多个子区间值以便查询时节约时间的数据结构。而LazyTag的设置使在单点修改节约了时间。

L1                            1-10(1)
                        /               \ 
L2              1-5(2)                     6-10(3)
            /           \              /           \
L3        1-3(4)       4-5(5)        6-8(6)          9-10(7)
        /      \        /   \        /    \        /    \
L4  1-2(8)     3(9)  4(10) 5 (11)  6-7(12) 8(13)  9(14) 10(15) 
    /     \                       /   \
L5 1(16)  2(17)                 6(24) 7(25)

上图即为1-10区间的线段树结构示意图

线段树结构将一个大区间，分为2个小区间并递归(左树>=右树)

因为我们要求区间的和，所以我们设置一个sum[cur] 存储以cur为编号的区间的和
并且设置一个LazyTag(懒标记)数组 cov[cur] (在后文中解释)

举例(结合代码看):

操作1,在区间1-7中每个数都加1：

在任何情况下添加x，都不能破坏线段树的性质与定义

1-7每个数添加1，

因为1号区间为1-10,覆盖整个1-7，故显然1号区间应的和应加上7 sum[1]+=7

因为2号区间为1-5,不能覆盖1-7整个区间，只含有1-5部分，故sum[2]+=5

因为3号区间6-10,与1-7有重叠部分,故应加上重叠部分的添加值(6-7) sum[3]+=2

接下来的情况与上文这两条相似，可能出现4种情况，与上文对应思考即可。

四种情况分别为：

1.需要添加的区间覆盖原本的区间

2.原本的区间覆盖需要添加的区间

3.需要添加的区间与原本区间有交集

4.需要添加的区间与原本区间无交集(什么也不用做)

而这仅是常规的方式,时间复杂度极大

在线段树的结构中,我们设置懒标记来保证时间复杂度

试着思考这样一个问题:现在对一颗线段树执行2个操作：

操作1为区间1-5中每个数+1;
操作2为区间1-3中每个数+2;

如果通过上文的方式,我们在执行操作1时会在 1-5加5 , 1-3加3 , 4-5加2

并对1-3和4-5的子区间执行相同的操作

有没有发现，操作1中对1-3区间每个数加了1，操作2中对1-3区间每个数加了2

而这两个操作是针对相同区间分别进行的，如果能够合并(即区间1-3每个数加3),可以大大降低复杂度！

故，我们在给区间1-5每个数添加1时，先加上5，然后在懒标记数组cor[cur]加上1

以记录曾经在1-5中加了1，且还未将这个1更新至子区间中。然后退出

而针对上文四种不同的区间关系,以及查询工作，有时候我们需要立即将懒标记中的值更新入sum中，故需要执行pushdown操作(将懒标记传递下去)

pushdown即是将根的cov值更新入两个叶子的sum中，并更新两个叶子的懒标记 然后将根的cov值变为0;

有时候，我们仅对子区间进行了更新，而为更新子区间父亲的值，面对这种两颗叶子的sum被更新后与根的sum值不同步，我们也需要
updown操作，将两个叶子的sum值统计入根的sum中。

实现

在开空间时，为简便计算且防止越界，常将数组开至标准空间的4倍

#define N maxn*4
int cov[N],int sum[N];

建树：

添加：

inline void updown(int cur){
        sum[cur]=sum[cur<<1]+sum[cur<<1|1];    
    }
inline void pushdown(int cur,int x){
        cov[cur<<1]+=cov[cur];
        cov[cur<<1|1]+=cov[cur];
        sum[cur<<1]+=cov[cur]*(x+1>>1);
        sum[cur<<1|1]+=cov[cur]*(x>>1);
        cov[cur]=0;
    }

inline void add(int l,int r,int L,int R,,int x,int cur){
        if(L<=l&&R<=r){
            cov[cur]+=x;
            sum[cur]+=(r-l+1)*x;
            return ;
        }
        pushdown(cur,r-l+1);
        int mid=l+r>>1;
        if(L<=mid) add(l,mid,L,R,x,cur<<1);
        if(R>mid) add(mid+1,r,L,R,x,cur<<1|1);
        updown(cur);
    }

inline int ask(int l,int r,int L,int R,int cur){
        if(L<=l&&R<=r)
            return sum[cur];
        pushdown(cur,r-l+1);
        int mid=l+r>>1,ans=0;
        if(L<=mid) ans+=ask(l,mid,L,R,x);
        if(R>mid) ans+=ask(mid+1,r,L,R,x);
        return ans;
    }

add：l-r是当前被操作区间的范围，L-R即为需要添加x的区间。

x是需要添加的值，cur是当前对应l-r区间的标号（最大的区间的cur为1）

if(L<=l&&R<=r)
即为上文情况(1)，需要操作的区间覆盖当前区间，故整个当前区间都需要修改(返回答案)

if(L<=mid) 即是需要操作的区间与当前区间的左儿子有重叠部分，故递归到左儿子

if(mid<R) 即是需要操作的区间与当前区间的右儿子有重叠部分，故递归到右儿子