线段树
给定一个序列,将他一直二分治到长度为
每个节点存自己所代表区间的信息(比如区间和),上面的区间可以通过下面的两个区间合并得到,长度为
从上到下给节点标号,根据二叉树的性质,假设当前节点编号是
节点数目最多有
但是节点编号的最大值是
void build(int l,int r,int p)//区间[l,r],节点编号是p
{
if(l==r)
{
ans[p]=a[l];
return;
}
build(l,mid,ls(p));
build(mid+1,r,rs(p));
ans[p]=ans[ls(p)]+ans[rs(p)];
}
build(1,n,1);
2
3
4
5
6
7
8
9
10
11
12
这样根据二分治结构对数组进行重建有两个好处:
一是任意一个区间都可以通过
通过树上的节点
首先这
其次,不会有相邻的三个区间长度是一样的,否则至少有两个可以合并成更大的区间
且所有区间长度都是子区间的
int query(int tl,int tr,int l,int r,int p)//查询区间是[tl,tr],当前节点代表的区间是[l,r],编号是p
{
if(tl<=l&&r<=tr) return ans[p];//如果当前区间完全包含在要查询的区间里
int sum=0;
if(tl<=mid) sum+=query(tl,tr,l,mid,ls(p));
if(tr>mid) sum+=query(tl,tr,mid+1,r,rs(p));
return sum;
}
2
3
4
5
6
7
8
第二个好处是,任意一个位置只包含在
void update(int pos,int l,int r,int p,int k)//给a[pos]+k
{
if(l==r)
{
ans[p]+=k;
return;
}
if(pos<=mid) update(pos,l,mid,ls(p),k);
else update(pos,mid+1,r,rs(p),k);
ans[p]=ans[ls(p)]+ans[rs(p)];//更新一下
}
2
3
4
5
6
7
8
9
10
11
当涉及到修改一个区间的时候,可以给涉及到的
比如如果是给一个区间都
当下次修改或者查询涉及到这个区间的,再顺便把这个修改更新到它的两个儿子上,这样可以实现
否则每个都将修改进行到叶子节点,那么每次修改都是
void pushdown(int l,int r,int p)
{
ans[ls(p)]+=(mid-l+1)*tag[p];
tag[ls(p)]+=tag[p];
ans[rs(p)]+=(r-mid)*tag[p];
tag[rs(p)]+=tag[p];
tag[p]=0;//放下去之后把标记消除。
}
void update(int tl,int tr,int l,int r,int p,int k)//给区间[tl,tr] 所有数字 +k
{
if(tl<=l&&r<=tr)
{
ans[p]+=(r-l+1)*k;//区间里每个数+k
tag[p]+=k;//打标记
return;
}
if(tag[p]!=0) pushdown(l,r,p);//如果有标记,在这里把修改更新到儿子上。
if(tl<=mid) update(tl,tr,l,mid,ls(p),k);
if(tr>mid) update(tl,tr,mid+1,r,rs(p),k);
ans[p]=ans[ls(p)]+ans[rs(p)];
}
int query(int tl,int tr,int l,int r,int p)//查询区间是[tl,tr],当前节点代表的区间是[l,r],编号是p
{
if(tl<=l&&r<=tr) return ans[p];//如果当前区间完全包含在要查询的区间里
int sum=0;
if(tag[p]) pushdown(l,r,p);
if(tl<=mid) sum+=query(tl,tr,l,mid,ls(p));
if(tr>mid) sum+=query(tl,tr,mid+1,r,rs(p));
return sum;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
线段树标记合并
省流:区间加
设置三个数组:
所以我们同时有两个标记,当要下放时,总要先放一个,再放另一个,该怎么编排这两个标记的顺序?
如果我们认为,一个节点应该是
给一个区间都加上
因为下放标记的时候还要乘以
这样就有分数了,不好。
所以最好是认为
进行区间加法时,应该
进行区间乘法时,应该
这样就没有分数,避免误差。
信息的性质
这样可以做到区间修改和区间查询,而且可以看出来,与树状数组做差求出特定区间不同,线段树求出区间信息是通过小区间合并的。
这要求信息满足以下要求:
1、信息可以快速合并(查询时)
2、信息和标记可以快速合并(修改时)
3、标记和标记可以快速合并(修改时和下放时)
更广泛一点说,信息和标记之间要有可合并(可加性),而不需要有可减性(不需要有逆元)
这个题就是因为没有数字逆元,所以适合用线段树
权值线段树
与值域树状数组类似,以数值为下标建立线段树,可以查询值域在一定范围内的数字的信息。
比如求逆序对,可以直接将树状数组换成线段树
势能线段树
省流:区间求和,区间开平方。
数值
要注意到
所以如果一个位置是
怎么跳过呢,在线段树上设置节点信息
如果全都是
否则递归进去,找到不是
void update(int tl,int tr,int l,int r,int p)//给[tl,tr] 开根号
{
if(vis[p]) return;
if(l==r)
{
a[l]=sqrt(a[l]);
ans[p]=a[l];
if(a[l]==1) vis[p]=1;
return;
}
if(tl<=mid) update(tl,tr,l,mid,ls(p));
if(tr>mid) update(tl,tr,mid+1,r,rs(p));
vis[p]=vis[ls(p)]&vis[rs(p)];
ans[p]=ans[ls(p)]+ans[rs(p)];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
其他跟势能有关的信息也可以用这种方法维护,比如区间取模(每次取模后数字小于原来的一半)。
线段树上二分
线段树天然是二分(二分治)结构
例如,有一个数组
设
修改就不多说了,标准套路
查询如下:
int query(int tl,int tr,int l,int r,int p)
{
if(l==r)//找到了位置
{
if(a[l]==0) return l;
return 0;
}
if(tag[p]) pushdown(p);//下放标记
if(ans[ls(p)]==mid-l+1) return query(tl,tr,mid+1,r,rs(p));//如果左区间是满的,去右边找
return query(tl,tr,l,mid,ls(p));//如果左区间不满,在左边找。
return pos;
//这里也是先在左边找,如果左边没找到再在右边找
}
2
3
4
5
6
7
8
9
10
11
12
13
查询全局第
以值域为下标建立一颗线段树,区间信息表示这个区间里面有多少个数字
int query(int l,int r,int p,int k)
{
if(l==r) return l;//找到数字了
if(ans[ls(p)]>=k) return query(l,mid,ls(p),k);
return query(mid+1,r,rs(p),k-ans[ls(p)]);
}
2
3
4
5
6
动态开点
当建立值域线段树时,有时候值域很大,又不方便离散化,可以进行动态开点。
只对涉及到的节点建立出来,不涉及到的节点不建立。
这样会导致节点编号不连续,所以要特别记录每个节点的左右儿子的编号
void update(int tl,int tr,int l,int r,int &p,int k)
{
if(!p) p=++tot;
if(tl<=l&&r<=tr)
{
ans[p]+=(r-l+1)*k;
tag[p]+=k;
return;
}
if(tag[p]) pushdown(l,r,p);
//son[p][0] 是左儿子编号,son[p][1] 是右儿子的编号
if(tl<=mid) update(tl,tr,l,mid,son[p][0],k);
if(tr>mid) update(tl,tr,mid+1,r,son[p][1],k);
ans[p]=ans[son[p][0]]+son[p][1]];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
练习题
P1020 [NOIP1999 提高组] 导弹拦截 优化动态规划