线段树学习笔记
线段树学习笔记
已知一个数列,你需要进行下面两种操作
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) 即是需要操作的区间与当前区间的右儿子有重叠部分,故递归到右儿子
本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。
本文永久链接: http://www.mayflyyh.com/archives/52
3条评论
yyh最强!!!!
我是igakki大佬!!!
测试一下