Mayflyyh
Mayflyyh
MayFlyyh's Blog
线段树学习笔记

线段树学习笔记

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

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) 即是需要操作的区间与当前区间的右儿子有重叠部分,故递归到右儿子
本文链接:http://www.mayflyyh.com/archives/52
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      学习笔记      线段树学习笔记
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

线段树学习笔记
线段树学习笔记 已知一个数列,你需要进行下面两种操作 1.将某区间每一个数加上x 2.求出某区间每一个数的和 线段树,即是将一个整区间分解成几小区间,保存多个子区间值…
扫描二维码继续阅读
2018-02-24