当前位置:   article > 正文

图解:什么是线段树?

堆式建树

作者简介:黄子桓,华师大三学生一枚,进场参加各类算法竞赛,并获得了挺多荣誉,耗费 3 天时间给大家贡献此文!

图文:黄子桓

编辑:景禹

致谢:感谢子桓的无私贡献,收到您的投稿已有时日,只是我工作时间紧张,未能尽早修改发布,还望理解!祝愿你早日找到自己理想的工作。

简介

线段树是在算法竞赛中常用来维护区间信息的数据结构,同时,线段树的理解难度较树状数组低(当然是在理解递归的前提下)。

线段树可以在 的时间复杂度内实现对数组的单点修改、区间修改、区间查询等操作。

下面以一个简单的例题进行介绍:

给定一个数组 arr[0 ... n-1],执行不超过10万次以下两个操作:

1、输出数组中 [left, right] 区间内的数的和,也就是 a[left] + a[l+1] + ... + a[right]

2、将数组 [left, right] 区间内的所有数更改为 k。

线段树的结构与建树

线段树将每个长度不为1的区间划分为左右两个区间,并递归处理,通过合并左右两个区间的信息来求得该区间的信息。

对于例题来说,我们想要得到的是指定区间里数的和,那么,我们要求的区间信息便是该区间数的和,合并左右两个区间的信息即是将两个区间的值进行相加。

例如对于数组 arr = [ 13 , 99 , 23 , 66 , 7 , 2 , 56 , 45 ] 而言:

数组长度为 8,以中点为分界点,划分为左右子区间:

mid = (left + right) / 2 ,则 [left, mid] 为左子区间,[mid + 1 , right]  为右子区间(如果区间长度是奇数,则左子区间比右子区间大1);接着,对子区间递归划分,直到区间长度为 1。

我们对数组 arr = [ 13, 99, 23 , 66 , 7 , 2 , 56 , 45 ] 执行上面提到的递归划分过程后:

在回溯的过程中,合并子区间的信息,即将子节点的值加起来:

此时一颗线段树其实就已经建成了,你可以将你的手机上下颠倒看一看这个图。

线段树的结构如下:

如何存储这个线段树呢?

最简单的方法是堆式建树

即像下面这样,我们可以用一个数组直接存储线段树的节点,节点在数组中下标如图:

由图,我们可以发现一个规律:

对于一个节点,设其在数组中下标为 ,则该节点的左子节点的下标为  ,右子节点的下标为  ,父节点的下标为  (取下界)。

建树的代码:

  1. int arr[100010];//原数组
  2. int tree[400010]; //线段树数组
  3. //建立线段树,[l, r]为节点代表的范围, p 为节点在线段树数组的下标
  4. void build(int left, int right, int p = 1)
  5. {
  6.     if(left == right)
  7.     {//区间长度为 1, 节点值即为原数组对应位置的值;
  8.         tree[p] = arr[left];
  9.         return;
  10.     }
  11.     int mid = (left + right)/2;
  12.     
  13.     build(left, mid, 2 * p); //递归处理左子区间
  14.     build(mid + right, right, 2 * p + 1); //递归处理右子区间
  15.     
  16.     tree[p] = tree[2 * p] + tree[2 * p + 1]; // 合并左右子区间的信息
  17. }

这里有一点需要注意:堆式建树的线段树的数组大小需要设为原数组大小的4倍,原理可参考

线段树需要开4倍区间大小的数组的原因 ,所以线段树节点数一定小于原区间长度的4倍,所以建树过程的时间复杂度为 量级。

区间查询

回到例题,建好树后,如何查询 [left, right] 区间内数的和?

只需要在线段树中找到一些节点,这些节点刚好能组成查询的区间,再合并这些节点的信息即可

(找到的节点要尽可能少)。

这里先放4张图,看一下查询过程以及我们需要查询的节点。

查询区间 [1, 5] :

查询区间的数的和即是 201+7=208 .

查询区间 [3, 6]:

查询区间的数的和即是 89+9=98

查询区间 [5, 6] :

查询区间的数的和即是 9

查询区间  [1, 7] :

查询区间的数的和即是 201+9+56=266

由图可以看出,在线段树中查询指定的区间,其实就是找到一些节点(也就是图中的粉红色节点),使这些节点恰好能组成查询的区间。

显然,查询操作所遍历的节点数(浅蓝色节点+粉红色节点)与树高成正比,即查询操作的时间复杂度为 .

为了查找这些浅蓝色节点,从根向下遍历,每遇到一个节点,可分为2种情况

1、当前节点代表的区间是询问区间的子集。

例如:询问区间为 [1, 7] ,当前节点代表的区间为 [1, 4] (大圆圈起部分)是询问区间的子集,则直接将此节点的值返回即可,区间 [5, 6][7] 也是一样。

可以发现,情况1的节点即是图中的粉红色节点。

2、除第一种情况外,判断询问节点与子区间是否有交集,若有,则递归处理。

例如:询问区间为 [1, 7] ,当前节点代表区间为  [1, 8] (大圆圈起部分)与询问区间有交集,则递归处理其左右孩子。

左子区间为 [1, 4] ,是询问区间 [1,7] 的子集,所以将其返回 sum = 201;

右子区间为  [5, 8]  ,与询问区间 [1,7] 有交集,递归调用其左右子节点;

[5,8]  的左子区间 [5,6] ,是询问区间 [1,7] 的子集,所以将其返回 sum = 201 + 9 = 210;

[5,8]  的右子区间 [7,8] ,与询问区间 [1,7] 有交集,递归调用其左右子节点;

[7,8] 的左子区间 [7] ,是询问区间的子集,所以将其直接返回 sum = 210 + 56 = 276;

[7,8] 的右子区间 [8] ,与询问区间不存在子集也不存在交集,回溯到根结点结束。

情况2其实就是图中浅蓝色节点,递归完成后合并信息并返回。

那么如何判断两个区间是否有交集?

如果询问区间的 端点 小于等于 当前节点区间的 分界点,则为左子区间相交。

比如当前结点区间为 [1,8],其分界点为 mid = (1+8)/2=4 ,查询区间为 [1,7] ,查询区间的左端点为 1 ,由于 1 < 4 ,所以查询区间与当前结点区间为左子区间相交。

如果询问区间的 端点 大于 当前节点区间的 分界点,则与右子区间相交。

比如当前结点区间为 [1,8],其分界点为 mid = (1+8)/2=4 ,查询区间为 [5,6] ,查询区间的右端点为 6 ,由于 6 > 4 ,所以查询区间与当前结点区间为右子区间相交。

只看两种情况的描述有点抽象,直接看整体的代码:

  1. int query(int nl, int nr, int l, int r, int p = 1)
  2. {//[nl, nr]为所访问区间,[l, r]为当前结点代表的区间
  3.     if(nl <= l && r <= nr)
  4.     {
  5.         return tree[p];
  6.     }
  7.     
  8.     int mid = (l + r) / 2;
  9.     int sum = 0;
  10.     if(l <= mid)
  11.     {
  12.         sum += query(nl, nr, l, mid, 2 * p);
  13.     }
  14.     if(r > mid)
  15.     {
  16.         sum += query(nl, nr, mid+1, r, 2 * p + 1);
  17.     }
  18.     return sum;
  19. }

单点修改

看完前两个步骤的代码,相信已经发现了:线段树的一系列操作就是通过递归不断缩小区间,直到找到所需的节点。

那么单点修改的操作就很明显了:找到对应的区间并修改,回溯时对沿途的节点更新。

我们以将数组 arr[4] 的值 66 修改为 8 进行说明,其中 "递归" 的过程就是找到从根节点 [1,8] 到要修改的结点的 [4] 的路径,而 的过程就是对路径上结点值的修改过程。

修改结点 [4] 的值为 8

修改结点 [4] 的父结点 [3,4] 的值为当前 [3] 的值 23 加上 [4] 的值 8 ,即 23 + 8 = 31 :

修改节点 [3,4] 的父结点 [1,4] 的值为当前 [3,4] 节点的值 31 和其兄弟节点[1,2] 的值 112 的和,即 112 + 31 = 143:

最后将根节点 [1,8] 的值修改为当前结点 [1,4] 及其兄弟结点 [5,8] 的和,即 143 + 110 = 253:

实现代码超级简单(这就是递归的魅力,代码简洁):

  1. void change_s(int idx, int k, int l, int r, int p = 1)
  2. {// 将arr[idx] 的值修改为 k, [l, r] 为当前结点代表的区间
  3.     if(l == idx && r == idx)
  4.     {
  5.         tree[p] = k;
  6.         return;
  7.     }
  8.     int mid = (l + r)/2;
  9.     
  10.     if(idx <= mid)
  11.     {
  12.         change_s(idx, k, l, mid, 2 * p);
  13.     }
  14.     else
  15.     {
  16.         change_s(idx, k, mid + 1, r, 2 * p + 1);
  17.     }
  18.     
  19.     tree[p] = tree[2 * p] + tree[2 * p + 1];
  20. }

单点修改的时间复杂度也为 .

区间修改、懒标记

接下来是线段树的重头戏:区间修改。显然,不可能通过一个个的单点修改来实现区间修改,这样时间效率还不如直接暴力修改。

区间修改的操作与之前的区间查询很相似,都是找到若干的区间能组成寻找区间

这里先引入一个新的概念:

懒标记

直接看栗子,我们现在想把数组中 [1,4] 中所有的数修改为 16

那么,我们通过递归找到了需要的节点(下图粉红色带圆圈的节点)

这时,我们知道,这个节点的值应该被修改为 64 (16*4=64)(16乘区间长度)。

这时,我们不需要继续往下递归,而是给这个节点打上一个标记。我们可以把这个标记设为16,意为这个区间的数已经被修改为16,如图所示:

然后回溯的过程中再更新结点的值:

从作用可以体会到为什么叫懒标记(就像别人给你家长一些钱说是给你和弟弟的压岁钱,然后家长就说先不给你们,等需要用的时候再给你们)

现在,我们再进行下一次修改,要将 [3, 8] 区间内的数修改为 7:

还是一样的操作,先找到需要的节点,但是,我们在找所需节点时遇到了带标记的节点(刚刚的区间修改操作打的标记),这时,我们把标记下传:

下传完毕后,继续查找,访问节点 [3,4] :

找到这些节点后,也是像刚刚一样,修改节点的值,并打标记。

注意:这里代表区间 [3,4] 的节点原来标记为 16 ,意为该区间已经被修改为16,现在我们想把这个区间更改为7,直接将标记修改即可。

我们想将 [3, 8] 区间内的数修改为 7 :

[3,4] 区间长度为2,所以节点值应改为 7 * 2 = 14,标记为 7;

[5,8] 区间长度为4,所以节点值应改为 7 * 4 = 28,标记为 7;

别忘记回溯时修改沿途节点:

在这里我猜可能有人会有疑惑:为什么加了标记以后就能保证区间修改时间复杂度为 .

其实很简单:很显然区间修改时遍历过的节点数(浅蓝色+粉红色)与区间查询时遍历的节点是一样的;那么,只有这 个节点需要下传标记,所以区间修改时间复杂度为   .

代码如下,当然,加入了懒标记后,之前说到的几个操作都有少许的变动,这里先给出区间修改的代码再将全部操作代码一起给出:

全部代码

线段树节点的构造

  1. struct seg{
  2.     int val, tag;
  3.     bool have_tag;
  4. }tree[400010]; //线段树数组
  5. int arr[100010]; // 原数组

下传标记的函数

  1. void push_tag_down(int p, int l, int r)
  2. {
  3.     if(tree[p].hava_tag)
  4.     { //如果当前结点的标记不为 0 ,将当前结点的标记下传
  5.         int mid = (l + r) / 2;
  6.         seg root = tree[p], ls = tree[2 * p], rs = tree[2 * p + 1];
  7.         //结点值为 标记值 * 区间长度
  8.         ls.val = root.tag * (mid -l + 1);
  9.         ls.tag = root.tag, ls.have_tag = true;
  10.         rs.val = root.tag * (r - mid);
  11.         rs.tag = root.tag, rs.hava_tag = true;
  12.         
  13.         root.hava_tag = false;
  14.     }
  15. }

区间修改的函数

  1. void change(int nl, int nr, int k, int l, int r, int p = 1)
  2. {// k为区间[l, r]内每个数的变化量
  3.    if(nl <=l && r <= nr)
  4.    { // 当该节点的区间是访问区间的子集
  5.        tree[p].val = (r - l + 1) * k;
  6.        tree[p].tag = k;
  7.        tree[p].hava_tag = true;
  8.        return;
  9.    }
  10.    push_tag_down(p, l, r); //访问到带标记的结点就下传标记
  11.    
  12.    int mid = (l + r) / 2;
  13.    if(nl <= mid) // 与左子区间相交
  14.    {
  15.        change(nl, nr, k, l, mid, 2 * p);
  16.    }
  17.    if(nr > mid)
  18.    {
  19.        change(nl, nr, k, mid + 1, r, 2 * p + 1);
  20.    }
  21.    
  22.    tree[p].val = tree[2 * p].val + tree[2 * p + 1].val;//回溯时更新
  23. }

加入懒标记后的建树函数

  1. void build(int l, int r, int p = 1)
  2. {//建立线段树,[l, r]为节点代表的范围 p 为节点在线段树数组下标
  3.     tree[p].tag = 0;
  4.     tree[p].hava_tag = false;
  5.     
  6.     if(l == r)
  7.     {
  8.         tree[p].val = arr[l];
  9.         return;
  10.     }
  11.     int mid = (l - r)/2 ;
  12.     build(l, mid, 2 * p); // 递归处理左子区间
  13.     build(mid + 1, r, 2 * p + 1); //递归处理右子区间
  14.     
  15.     tree[p].val = tree[2 * p].val + tree[2 * p + 1].val; //合并左右子区间的信息
  16. }

加入懒标记后的查询函数

注意,查询函数中同样需要下放标记!

  1. int query(int nl, int nr, int l, int r, int p = 1)
  2. {//[nl, nr]为所访问区间, [l, r]为当前节点代表的区间
  3.     if(nl <= l && r <= nr) // 当该节点的区间是访问区间的子集
  4.     {
  5.         return tree[p].val;
  6.     }
  7.     
  8.     push_tag_down(p, l, r); // 访问到就下传标记
  9.     
  10.     int mid = (l + r) / 2;
  11.     int sum = 0;
  12.     if(l <= mid) //与左子区间相交
  13.     {
  14.         sum += query(nl, nr, l, mid, 2 * p);
  15.     }
  16.     if(r > mid) // 与右子区间相交
  17.     {
  18.         sum += query(nl, nr, mid + 1, r, 2 * p + 1);
  19.     }
  20.     
  21.     return sum;
  22. }

注:这里没有单点修改的代码

因为单点修改可以通过调用区间修改函数来修改一个长度为1的区间来实现。且纯单点修改的代码跟区间修改的几乎相同(懒)。

主函数中的调用

  1. int main()
  2. {
  3.     int n, m, opt, l, r, k;
  4.     cin>>n>>m;
  5.     for(int i = 1; i <= n; i++) cin >> arr[i];
  6.     build(1, n);
  7.     for(int i = 1; i <= m; i++)
  8.     {
  9.         cin>>opt>>l>>r;
  10.         if(opt==1)
  11.         {
  12.             cin>>k;
  13.             change(l,r,k,1,n);
  14.         }
  15.         else{
  16.             cout<<query(l,r,1,n);
  17.         }
  18.     }
  19.     return 0;
  20. }

区间合并操作与懒标记的运用

介绍完3个主要操作,线段树的主体已经介绍完了,大家不要被这100多行的代码吓到,我这里是为了打注释留了很多空位,大家实际打的过程中每个函数只有15行左右!

接下来是一些小的进阶。

通过上面的几个操作,相信大家已经发现了线段树的核心:

通过对小区间信息的合并来得到大区间的信息,查询时将几个区间合并即可得到指定区间的信息。

同时,对懒标记的巧妙运用可以对很多信息进行维护,此处给出几个例题,熟悉线段树的使用

基础:

https://www.luogu.com.cn/problem/P3372(例题的变形)

https://www.luogu.com.cn/problem/P3373(懒标记的使用)

进阶:

https://www.luogu.com.cn/problem/P6242

对于区间信息合并的进一步讨论

对于例题而言,合并两信息只需要把两个子区间得到的数相加就可以了,但是实际情况中不可能只让我们求出一堆数的和,比如下面这道题:

https://www.luogu.com.cn/problem/P4198

这个就留作思考题啦,这里不作展开(我也是看了题解才会的qwq)

权值线段树

顾名思义,权值线段树就是统计权值的线段树!

上一道简单的例题

相信接触过平衡树的同学直接就看出来了:这不就是平衡树的模板题嘛

但是在考场上写动不动就一两百行的平衡树未免太折磨人了!

下面来介绍权值线段树的写法

在一开始的例题中,线段树一个节点记录的是这个节点对应的区间的数的和。在权值树里,节点记录的则是对应区间的数出现了几次!

例如,对于集合 [1,3,3,5,4,8] 权值线段树的结构为这样:

节点记录的是节点所代表的区间的数的出现次数,比如 [1,3,3,5,4,8]  2 中 1 出现 1次,2、6 和 7 出现 0 次,3 出现 2 次 , 4 出现 1 次,5 出现 1 次,8 出现 1 次,所以叶子结点中表示的就是对应数组出现次数,其他结点代表区间内所包含数的出现次数。

那么,题目中的插入的数的值域可是有 啊,怎么能开下这么多的空间?

所以,在这里不能使用堆式建树

动态开点

从上面的图里可以看出有一些点是不需要用到的

夸张一点:

这些黑色节点我们一开始不需要,等到需要用到的时候再开辟就可以了!

这里我先介绍竞赛中比较常见的,较为容易的实现方法:

我们可以声明一个足够大的线段树数组,再声明一个变量 cnt(记录用过的节点数),当我们访问到一个没访问过的节点时,令 cnt++,则线段树数组中下标为 cnt 的节点即为新节点,只需要想办法让新节点跟以前的节点联系上就好了

  1. struct seg {
  2.     int ls, rs, val;
  3.     seg(int v=0,int l=0int r=0):val(v),ls(l),rs(r){};
  4. };
  5. seg t[MAX_N];
  6. int cnt;
  7. inline void pushup(int o){
  8.     t[o].val = t[t[o].ls].val + t[t[o].rs].val;
  9. }
  10. void change(int &o, int l, int r, int k, int v)
  11. {
  12.     // 将 k 的出现次数改变 v,[l, r]为当前节点代表的区间
  13.     if(!o) o = ++cnt;
  14.     if(l == r)
  15.     {
  16.         t[o].val += v;
  17.         return;
  18.     }
  19.     int mid = (l + r) / 2;
  20.     if(k <= mid) change(t[o].ls, l, mid, k, v);
  21.     else change(t[o].rs, mid + 1, r, k, v);
  22.     pushup(o);
  23. }

这里的change 函数与前面的逻辑一致,除了这句话

if(!o) o = ++cnt;

而且这里的 o 是以引用的方式传进来的,其实这里的o就是节点在线段树数组中的下标

回顾代码,在线段树数组被声明时,每一个节点的左右子节点都为0,那么,我们在递归的过程中遇到了 o 为零,就可以确定这个节点未被使用。

而以引用的方式传入,则可确保原值被赋值,即 t[o].lst[o].rs

即实现了将新开辟的节点与其父节点相联系,理解了change函数,插入与删除操作就很简单了

如果要插入 x ,则执行 change ( 1 , -1e9 , 1e9 , x , 1 )

如果要删除 x,则执行 change ( 1 , -1e9 , 1e9 , x , -1 )

设区间长度为 n,则线段树的树高是 ,在这里区间长度即是值域的大小 ,每次操作最多产生新节点数即是 ,30个左右,所以空间是绝对足够的。

如果想要追求效率的话,可以用离线算法,将所有询问到的数记录下来并离散化,再使用权值线段树,感兴趣的话可以自己实现一下,接下来的操作如果理解了一开始的线段树的介绍后就是很简单的了!

查找排名第k的数

访问到一个节点时,记录左子区间的数的次数为 num,如果 k <= num,则向左子节点递归;否则,将k减去num,再向右子节点递归 。

  1. int query_kth(int o, int l, int r, int k)
  2. {
  3.     if(l == r){
  4.         return l;
  5.     }
  6.     int mid = (l + r)/2;
  7.     int num = t[t[o].ls].val;
  8.     if(k <= num)
  9.     {
  10.         return query_kth(t[o].ls, l, mid, k);
  11.     }
  12.     else
  13.     {
  14.         return query_kth(t[o].rs, mid + 1, r, k - num);
  15.     }
  16. }

为什么向右子节点递归时k要减去 num ?

这个函数其实是求以 o 为根的树中第 k 的数,又 num 代表的是左子区间的数的次数,那么右子区间的第 k-num 的数就是以 o 为根的子树的第 k 的数了 .

查询数 k 的排名

设当前节点代表的区间的中点为 mid ,当 k <= mid 时,向左子节点递归;否则,设左子区间的数的次数为num,向右子节点递归,再将得到的数加上 num 并返回 。

  1. int query_rk(int o, int l, int r, int k){
  2.     if(l == r){
  3.         return 1;
  4.     }
  5.     int mid = (l + r)/2;
  6.     if(k <= mid)
  7.     {
  8.         return query_rk(t[o].ls, l, mid, k);
  9.     }
  10.     else
  11.     {
  12.         return t[t[o].ls].val + query_rk(t[o].rs, mid+1, r, k);
  13.     }
  14. }

查询前驱和后继的操作很简单,这里就留作作业啦! 一开始时说到,这是竞赛时可用的,较为简短的版本!

对于动态开点,vector、指针,都是可行的方法;用指针的话,可以避免类似 t[t[o].ls].val 这种写法,但是也会带来较大的调试难度!这里就不作更多的展开了,大家可以自己尝试不同的写法!

写在结尾:

本来的计划最后面还有zkw线段树,和可持久化的介绍,但是突然发现已在 word 中写了 20 多页。。。

那么本文就先这样结束啦,如果我讲解的有些地方不太周全欢迎大家指点,如果喜欢这个文章的话欢迎点个赞啦嘻嘻~~

推荐阅读:

漫画:什么是树状数组?

图解:什么是哈希?

作者:景禹,一个追求极致的共享主义者,想带你一起拥有更美好的生活,化作你的一把伞。


声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/179996
推荐阅读
相关标签
  

闽ICP备14008679号