线段树

线段树是一种算法竞赛里常见的数据结构,经常被用来维护区间信息,其可以在O(logn)O(logn)的时间里查询、修改区间信息。

一、建树

线段树将每个区间都划分成左右两个区间,直到不可再分为止,假如建一棵区间为(15)(1-5)的线段树,其结构应为下图。

一个线段树的结构图

根据线段树的结构,我们可以很轻松的写出线段树的建树函数。

代码实现-时间复杂度O(nlogn)O(nlogn)
1
2
3
4
5
6
7
8
9
10
11
12
13
void build(gg l,gg r,gg p) //using gg=long long;
{
if(l==r) //当只有一个点时将值赋给树节点
{
tree[p]=v[l];
return;
}
gg mid=(l+r)/2;
build(l,mid,p*2);
build(mid+1,r,p*2+1);
tree[p]=tree[p*2+1]+tree[p*2]; //求出当前区间的区间和
return;
}

二、区间查询

处理一次查询时,我们可以递归不断减小当前区间,对于每一次减小区间,我们判断当前区间的左右孩子区间是否与需要求的区间有交集,如果有就递归这个孩子区间,最后得到的返回值即是当前区间的区间和。

代码实现-时间复杂度O(logn)O(logn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
gg getsum(gg l,gg r,gg nl,gg nr,gg p)
{
if(nl>=l&&nr<=r) //当前区间为子区间时返回当前区间的区间和
{
return tree[p];
}
gg mid=(nl+nr)/2,sum=0;
if(mid>=l)
{
sum=getsum(l,r,nl,mid,p*2);
}
if(mid+1<=r)
{
sum+=getsum(l,r,mid+1,nr,p*2+1);
}
return sum; //返回总区间和
}

三、区间修改

暴力修改O(n)O(n)的时间复杂度是绝对不能接受的,我们可以维护一个tagtag数组,称为懒惰标记,在要修改的区间打一个懒惰标记,每次需要用到这部分的时候再进行下传操作,就可以实现在O(logn)O(logn)的时间复杂度里修改一段区间!

代码实现-时间复杂度O(logn)O(logn)

1
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
void update(gg l,gg r,gg nl,gg nr,gg p,gg k) //k为修改的值
{
if(nl>=l&&nr<=r)
{
tree[p]+=k*(nr-nl+1);
tag[p]+=k;
return;
}
gg mid=(nl+nr)/2;
if(tag[p]) //遇到标记后下传
{
tree[p*2]+=tag[p]*(mid-nl+1);
tree[p*2+1]+=tag[p]*(nr-mid);
tag[p*2]+=tag[p];
tag[p*2+1]+=tag[p];
tag[p]=0;
}
if(mid>=l)
{
update(l,r,nl,mid,p*2,k);
}
if(mid+1<=r)
{
update(l,r,mid+1,r,p*2+1,k);
}
tree[p]=tree[p*2+1]=tree[p*2]; //上传更改
return;
}

添加懒惰标记后,区间查询也要做出相应的更改

1
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
gg getsum(gg l,gg r,gg nl,gg nr,gg p)
{
if(nl>=l&&nr<=r) //当前区间为子区间时返回当前区间的区间和
{
return tree[p];
}
gg mid=(nl+nr)/2,sum=0;
if(tag[p]) //遇到标记后下传
{
tree[p*2]+=tag[p]*(mid-nl+1);
tree[p*2+1]+=tag[p]*(nr-mid);
tag[p*2]+=tag[p];
tag[p*2+1]+=tag[p];
tag[p]=0;
}
if(mid>=l)
{
sum=getsum(l,r,nl,mid,p*2);
}
if(mid+1<=r)
{
sum+=getsum(l,r,mid+1,nr,p*2+1);
}
tree[p]=tree[p*2+1]+tree[p*2];
return sum; //返回总区间和
}

线段树练习题

LuoGu P3372

LuoGu P1253

LuoGu P3373

感谢阅读!