【数据结构】线段树

线段树

线段树是什么?

线段树是一种能让你代码强行增加50行的极容易爆炸的万金油数据结构,用于优雅暴力地解决对一个区间上满足区间可加性(即可由两个子区间的信息得到当前区间信息)区间修改和区间查询问题。

结构:

将区间划分为左端点到中点(即左子区间)和中点+1到右端点(即右子区间)的两个子区间,然后对两个子区间继续划分,直到划分到单个元素(即左端点=右端点)

示意图:
c0dd297d009ddb5d3d37da29c291da7c07e3cb5a0c40b2ec.png

不难看出线段树除了最下面一层,其他的部分一定是一颗完全二叉树,这意味着整棵树可以使用“父子二倍法”(左儿子编号为父亲编号 $\times$ 2,右儿子编号为父亲编号 $\times$ 2 $+$ 1)存储在一个数组中。同时,因为还要考虑到最后一层,数组的大小应开到n $\times$ 4大小。

线段树的一个很重要的性质就是一棵[1~n]的线段树的深度最大为 $log_2 n+1$,这也意味着线段树可在$O(logn)$的时间复杂度内完成所有操作。


实现

洛谷P3372 【模板】线段树 1的维护最大值为例
首先,我们给线段树中每个元素一个sum变量存储该元素代表区间的区间和,叶子结点的sum是原数组当前位置的值,非叶节点的sum是其左右子节点sum的和,如当原数组为
3dd6bf7464e1e756f.png

时,对应的线段树为2cd920dd97dbafe0d.png

节点结构体:

1
2
3
4
5
6
7
8

struct segmenttree{
int l,r,sum,add;
#define l(x) tree[x].l //当前区间左端点
#define r(x) tree[x].r //当前区间右端点
#define sum(x) tree[x].sum //区间和
#define add(x) tree[x].add //延迟标记(这个后面会讲)
}tree[maxn];

操作

操作有递归和非递归两种形式,递归式相对于非递归式更直观,因此这里讲解递归式。

非递归式和递归式本同末异,考试时按照数据规模而定。

建树:

按照之前提到的定义,从根节点([1~n])向左右两边递归,递归到叶子结点就将该节点sum设为其在原数组中对应的值,回溯时将当前节点的sum设为其左右子节点sum的和。

代码:

1
2
3
4
5
6
7
8
9

void build(int p,int l,int r)
{
l(p)=l;r(p)=r; //设置端点
if(l==r) { sum(p)=num[l]; return;} //如果是叶子节点
int mid=((l+r)>>1); //位运算,右移1位相当于/2,左移同理
build(p<<1,l,mid); //向左递归
build(p<<1|1,mid+1,r) //向右递归,一个偶数|1相当于+1
}

复杂度为$O(nlogn)$

区间查询:

设查询区间的左端点为 $l$,右端点为 $r$,当前区间的左端点为 $l_1$,右端点为 $r_1$,中点为$mid$ ,则

  • 当 $l \leq l_1$ 且 $r \geq r_1$时 直接返回当前区间的sum,因为当前区间已经涵盖了子区间的全部信息
  • 当 $l \leq mid$时,向左递归,$r_1=mid$(此时查询区间一定涵盖左子区间的一部分)
  • 当 $r > mid$时,向右递归,$l_1=mid+1$ (此时查询区间一定涵盖右子区间的一部分)

代码:

1
2
3
4
5
6
7
8
9
10

int query(int p,int l,int r)
{
if(l<=l(p) && r>=r(p)) return sum(p); //完全包含
int mid=((l(p)+r(p))>>1);
int ans=0;
if(l<=mid) ans+=query(p<<1,l,mid); //向左递归,累加左子树答案
if(r>mid) ans+=query(p<<1|1,mid+1,r); //向右递归,累加左子树答案
return ans;
}

复杂度为$O(logn)$

区间修改与延迟标记:

当进行区间修改时,我们依然可以设查询区间的左端点为 $l$,右端点为 $r$,当前区间的左端点为 $l_1$,右端点为 $r_1$,中点为$mid$,同时查询操作也满足这两条性质:

  • 当 $l \leq mid$时,向左递归,$r_1=mid$(此时查询区间一定涵盖左子区间的一部分)
  • 当 $r > mid$时,向右递归,$l_1=mid+1$ (此时查询区间一定涵盖右子区间的一部分)

但当出现完全覆盖的情况时,事情就变得不那么简单了,一个一个深入更新会使单次修改的复杂度高达 $O(n)$,这是我们所无法接受的。这时,我们就要引入延迟标记

试想一下,如果你花费很大的代价更新了节点p的子树,但在之后的查询中却根本没有访问到它们,那更新p的子树岂不是白费力气?因此,我们可以在区间修改出现“完全覆盖”情况时也直接返回,但要给当前节点打上一个代表“当前节点已被更新,但其子节点尚未被更新”的延迟标记(这里取名add)。(如果操作是相容的(如加法),那在打标记前无需下传原来的标记。如果操作是不相容的(如赋值),那在打标记前需下传原来的标记。)

在以后的查询操作中,如果遇到了有延迟标记的节点,便将其的两个子节点更新并打上延迟标记,并擦除当前节点的延迟标记(即将延迟标记下传一层),这样就减少了大量无用的更新操作 (虽然本质上依旧是暴力)

代码:

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
29
30
31
32
33
34
35
36
37
38

void spread(int p) //下传标记
{
if(add(p))
{
add(p<<1)+=add(p);
add(p<<1|1)+=add(p);
sum(p<<1)+=add(p)*(r(p<<1)-l(p<<1)+1); //区间和增量=数值增量*区间长
sum(p<<1|1)+=add(p)*(r(p<<1|1)-l(p<<1|1)+1); //区间和增量=数值增量*区间长
add(p)=0;
}
}

int query(int p,int l,int r)
//更新后的区间查询,增加了下穿标记的操作
{
if(l<=l(p) && r>=r(p)) return sum(p); //完全包含
spread(p);//下传标记
int mid=((l(p)+r(p))>>1);
int ans=0;
if(l<=mid) ans+=query(p<<1,l,mid);
if(r>mid) ans+=query(p<<1|1,mid+1,r);
return ans;
}

void update(int p int l,int r,int c)
{
if(l<=l(p) && r>=r(p)){
sum(p)+=c*(r(p)-l(p)+1); //区间和增量=数值增量*区间长
add(p)+=c;
return;
}
spread(p);//下传标记
int mid=(l(p)+r(p))>>1;
if(l<=mid) update(p<<1,l,r,c); //更新左子树
if(r>mid) update(p<<1|1,l,r,c); //更新右子树
sum(p)=sum(p<<1)+sum(p<<1|1); //更新当前点
}

复杂度为$O(logn)$


例题:

文章作者: 1379号监听员
文章链接: https://listener1379.site/2019/【数据结构】线段树/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 1379号监听站
支付宝打赏
微信打赏