【普及/DS】线段树入门基础题

[【基础DS】线段树详细入门笔记 ](https://www.luogu.com.cn/blog/AlanWalkerWilson/Segment-tree-detailed-note) ## Update 更新了一系列省选小清新线段树题。 # 线段树学习笔记 > $\quad$此学习笔记仅供自己学习与复习，由于本文作者是个非常弱的蒟蒻，所以他会花大量的时间解释一些极其简单的内容，所以如果您已经较为熟悉线段树，那么您完全不必看下去。 > $\quad$这篇文章在经过大家的审查（阅读）一段时间后也许会成为文文算法报的一部分呢，欢迎大家指出文中的不足，点出其中的错误和可以改进的地方，感谢大家的阅读。 如果在阅读本文前，您已经阅读过以下文章而有一些不理解的话，希望这篇文章能帮到你。 **相关博文：** - [Limit 的博客 - 线段树学习笔记](https://www.luogu.com.cn/blog/Limit/SegmentTree) - [花姐姐的博客 - Senior Data Structure · 浅谈线段树（Segment Tree）](https://www.luogu.com.cn/blog/pks-LOVING/senior-data-structure-qian-tan-xian-duan-shu-segment-tree) - [Dijkstra_Liu 的博客 - 线段树 从入门到进阶](https://www.cnblogs.com/jason2003/p/9676729.html) - [Xenny 的博客 - 线段树详解](https://www.cnblogs.com/xenny/p/9801703.html) - [OI-Wiki - 线段树](https://oi-wiki.org/ds/seg/) ## $1.0$ 线段树结构 说在前面： > $\quad$线段树是一个二叉树。 之所以称线段树为树主要是因为他符合**树形结构**，且是一个二叉树，而前面的线段两个字主要是因为他的结构像是把一条线段一次次分开，根节点是一条线段的长度，而他的两个子节点分别代表这条线段的一部分，左半边和右半边（他们不一定相等），而对于这两个子节点，又分别分为两部分（在最下面的节点可能不继续分割），这样层层递归，就是线段树的结构。 此处要注意，百度说线段树是二叉搜索树的说法并不准确，感谢 lmpp 神仙指出了这一错误： - BST（二叉搜索树）的节点左儿子比自己小，右儿子比自己大。 - 线段树维护的是区间，于此无关。 - 线段树并不一定是完全二叉树，但接下来的讲解以完全二叉树为背景便于理解。 - 经过了解，这是一个常见的误区，请一定区分。 do\_while\_true： - BST的父节点小于右孩子，线段树的父节点大于等于右孩子（因为右孩子表示的区间是父节点的表示的区间的子区间） Binary\_Search\_Tree： - 线段树是leafy tree而BST不是。 请注意这个易错点。  仔细观察上面这个图片，我们所需要存储的数组时紫色方框的数组，即 $a$，而我们所要建立的线段树是红色方框的树，也就是 $d$。接下来我们先对这张图进行着重讲解。 首先观察这个 $d$，你可以发现每一个父节点的值都是他两个子节点的和，为了方便理解，我们从 $d_8$ 和 $d_9$ 两个叶子结点开始向上讲解。由于 $d_8$ 仅代表了 $a_1$ 一个数，所以他的区间（黄色字）就是 $1\sim 1$，也就是这个区间仅仅包含了下标为 $1$ 的数组元素。同理，$d_9$ 也仅仅包含了下标为 $2$ 的元素，这时候他的值直接等同于 $a_2$，即 $11$。 接着我们看看他的父节点，也就是 $d_4$，他的值是 $d_8+d_9=21$，也就是 $a_1+a_2$，仔细观察他的区间，因为包括了 $a_1$ 和 $a_2$ 所以他的区间就是 $1\sim 2$，同理不断合并之后最后根节点的值就是他们的和，而其区间就是 $1\sim 5$。 可以表示为： $$d_1=\sum\limits_{m=1}^{n}a_m=a_1+a_2+\cdots+a_{n-1}+a_n$$ 如果看不懂中间的式子可以不看，意思就等同于右边一长串，您只要知道他是所有数组元素的和就行了。 ## $2.0$ 线段树的建立 而建立这个树的内容也是类似的，如要建立 $d_1$，则我们必须先建立 $d_2$ 和 $d_3$ 然后才能得到 $d_1$ 的值，同理，我们必须从叶子结点开始一点点向上建立，才能够完整地将线段树建立起来。 步骤的图片由于过于占据篇幅就不放置了，可以自行查阅 OI-Wiki。 ```cpp void build(int s,int t,int p){ //对 [s,t] 区间建立线段树,当前根的编号为 p if(s==t){//如果区间已经建立完毕 d[p]=a[s]; return; }//如果已经建立完毕就回溯 int m=(s+t)/2;//折半建树 build(s,m,p*2); build(m+1,t,p*2+1); //递归对左右区间建树 d[p]=d[p*2]+d[p*2+1];//等于两个子节点的和 } ``` 这里必须要说明的是，线段树是完全二叉树（或者说基本是），即一行一行的数，不会有数空的地方，或者说： > 一棵深度为 $k$ 的有 $n$ 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 $i(1\le i\le n)$ 的结点与满二叉树中编号为 $i$ 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。 对于这样的**完全二叉树**，存在性质，即编号为 $n$ 的节点的两个子节点分别为 $2n$ 和 $2n+1$，带入到建树过程即 $d_n=d_{2n}+d_{2n+1}$，这就是最后一行的作用。这种存储方法我们称之为**堆式存储**，按照这种方式存储的话，空间最大为：$2^{\left\lceil\log n\right\rceil+1}$，而通常我们可以直接开 $4$ 倍空间。 通过这样的方式我们完成了线段树的搭建，接下来应该要讲区间查询了。 ## $3.0$ 线段树区间查询 简单来说，区间查询有以下几种可能，首先他会给定一个区间 $[l,r]$，即从 $l$ 到 $r$ 的范围内，求： - 区间最大值（区间 $\max$） - 区间最小值（区间 $\min$） - 区间和 那么我们挑出区间和来讲解一下。 再看一下这张图：  如果给定的区间是 $[1,3]$ 的话非常简单，只要查询 $d_2$ 就可以获取到他们的和，即 $33$，而于此类似（即可以直接查询到的区间值）的还有： $$[1,5],[1,3],[4,5],[1,2],[1,1],[2,2],[3,3],[4,4],[5,5]$$ 总共有 $9$ 个，分别对应 $d_1$ 到 $d_9$，这些是能直接查询到的，当然也有不能查询到的，即需要拆成一些小区间，并获取这些区间的答案来得到我们所需要的值，比如： > 如果要查询的区间为 $[3,5]$，此时就不能直接获取区间的值，但是 可以拆成 $[3,3]$ 和 $[4,5]$，可以通过合并这两个区间的答案来求得这个区间的答案。 > >——摘自 OI-wiki 这就是我们如何获取答案，也就是说，当我们找到了一些可以直接获取的答案之后，我们可以通过合并他们的区间来获得我们对应的区间，这一过程理解起来很容易，但是代码也不怎么简单，所以还是看一看。 ```cpp int getsum(int l,int r,int s,int t,int p){ //[l,r]为查询区间,[s,t]为当前节点包含的区间,p为当前节点的编号 if(l<=s&&t<=r)return d[p]; //如果当前区间是询问区间的子集时，返回当前区间的和 int m=(s+t)/2,sum=0; if(l<=m)sum+=getsum(l,r,s,m,p*2); //如果左儿子的区间[l,m]与询问区间有交集,则递归查询左儿子 if(r>m)sum+=getsum(l,r,m+1,t,p*2+1); //如果右儿子的区间[m+1,r]与询问区间有交集,则递归查询右儿子 return sum; } ``` 简单来说，就是一个递归查找的过程，步骤如下： - 如果我现在查到的这个区间是答案的一部分，就返回一下这个和。 - 如果我现在这个区间的左儿子和答案区间有共同的部分，就去搜索他，并且进一步拆分直到左儿子的某些子孙完全是答案的一部分（也就是说不存在“是左儿子的一部分但是不是答案一部分的和”）。 - 对右边做同样的步骤。 - 得到了所有的和，返回这个和。 我知道这个步骤理解起来有些困难，但是这是非常重要的概念，在继续做题或者学习之前您务必确保您知道这个概念。 您可能有疑问，这样一找到就返回感觉像是碰运气啊，不会**有遗漏或者有重复**吗？事实上，我们不能按照正常的逻辑顺序来看一个递归的程序，要知道，第一个判断是基于下面两个递归调用的，我们调用的时候就确定了两个子树分别代表左边一半和右边一半，那么它就不会有重复出现，且我们不断调用，一定能够穷尽整个线段树，可以感性理解一下。 或者是，递归时 $s\sim m$ 和 $m\sim t$ 本身就是两个互不重合但是完全包含了 $s\sim t$ 的所有元素的集合，所以能够做到**不遗漏、不重复**。 ## $4.0$ 区间修改及懒惰标记 区间修改 $[l,r]$ 如果不管时间复杂度的话其实很简单，只要将其中的每一个节点都遍历并修改一次就行了，但是这样总是太慢了，时间复杂度根本不能承受，所以我们为了使其的运行速度在一个可以接受的范围内，我们引入一种“**懒惰标记**”（您在其他文本中看到的 lazy 标记大致也是此物），这里大致给大家介绍一下。 （注：因为 OI-Wiki 的故事太曲折离奇，就简化了） > A（父亲节点）：我这里的区间加了 $2$，你们都加 $2$。 > > B（左儿子）：好的。 > > C（右儿子）：但是这样太慢了，我们的子孙也都要加 $2$ 啊。 > > A（父亲）：那我就标记一下我欠你们这些，以后再还。 简单来说，做一个懒惰标记就像写一张欠条，标志着这些节点还需有一定的变化，但是暂时不进行处理，这样的过程我们~~还是借用~~看图看看：      这张图中，$d$ 还是线段树本身的值，而 $b$ 是懒惰标记数组的值，显然，当我们需要查询下面的两个儿子的时候，就要及时地将欠下的钱还回去，也就是根据懒惰标记来将所查询部分的值更新。 我们称之为**下传懒惰标记**。   加上的值是 $1$ 因为他所代表的区间只有一个元素，所以是 $1$。 再回顾一开始的根节点，因为所代表的的区间是 $[1,2]$，所以应该会有 $2\times 1$。 同理，一个有 $n$ 个元素的区间，若修改值为 $k$，则他的 $d$ 为 $n\times k$。懒惰标记所标记的内容仅仅是修改量，即欠每个儿子多少钱，只要懒惰标记大于 $0$ 就一定是欠了钱。  由此我们可以得到，区间 $[1,1]$ 的值为 $1$。 这里提一下新手可能会有的误区，其实线段树的查询和修改都是从根节点开始的。 代码实现依然有难度，所以贴一下代码： ```cpp //区间修改 void update(int l,int r,int c,int s,int t,int p){ //[l,r]为修改区间,c为被修改的元素的变化量,[s,t]为当前节点包含的区间,p为当前节点的编号 if(l<=s&&t<=r){ d[p]+=(t-s+1)*c;//元素个数*修改量 b[p]+=c;//更新 return; }//当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改 int m=(s+t)/2; if(b[p]&&s!=t){ //如果当前节点的懒惰标记非空,则更新当前节点两个子节点的值和懒标记值 d[p*2]+=b[p]*(m-s+1);//更新量 d[p*2+1]+=b[p]*(t-m);//更新量 b[p*2]+=b[p];b[p*2+1]+=b[p];//更新懒惰标记，下传给子节点 b[p]=0;//清空当前节点的标记 } if(l<=m)update(l,r,c,s,m,p*2); if(r>m)update(l,r,c,m+1,t,p*2+1); d[p]=d[p*2]+d[p*2+1];//合并出根节点 } ``` 区间查询： ```cpp //带有懒惰标记的区间求和 int getsum(int l,int r,int s,int t,int p) { //[l,r]为查询区间,[s,t]为当前节点包含的区间,p为当前节点的编号 if(l<=s&&t<=r)return d[p]; //当前区间为询问区间的子集时直接返回当前区间的和 int m=(s+t)/2; if(b[p]){//如果当前节点的懒惰标记非空,则更新当前节点两个子节点的值和懒标记值 d[p*2]+=b[p]*(m-s+1); d[p*2+1]+=b[p]*(t-m); b[p*2]+=b[p]; b[p*2+1]+=b[p];// 将标记下传给子节点 b[p]=0;//清空当前节点的标记 }int sum=0; if(l<=m)sum=getsum(l,r,s,m,p*2); if(r>m)sum+=getsum(l,r,m+1,t,p*2+1); return sum; } ``` 区间修改为某个特定值而非加上某个值： ```cpp void update(int l,int r,int c,int s,int t,int p){ if(l<=s&&t<=r) { d[p]=(t-s+1)*c; b[p]=c; return; }int m=(s+t)/2; if(b[p]){ d[p*2]=b[p]*(m-s+1); d[p*2+1]=b[p]*(t-m); b[p*2]=b[p*2+1]=b[p]; b[p]=0; }if(l<=m)update(l,r,c,s,m,p*2); if(r>m)update(l,r,c,m+1,t,p*2+1); d[p]=d[p*2]+d[p*2+1]; }int getsum(int l,int r,int s,int t,int p){ if(l<=s&&t<=r)return d[p]; int m=(s+t)/2; if(b[p]){ d[p*2]=b[p]*(m-s+1); d[p*2+1]=b[p]*(t-m), b[p*2]=b[p*2+1]=b[p]; b[p]=0; }int sum=0; if(l<=m)sum=getsum(l,r,s,m,p*2); if(r>m)sum+=getsum(l,r,m+1,t,p*2+1); return sum; } ``` 这里贴一下 OI-Wiki 里的几个线段树的优化（作者还在学习，并未完全掌握）： - 在叶子节点处无需下放懒惰标记，所以懒惰标记可以不下传到叶子节点。 - 下放懒惰标记可以写一个专门的函数 `pushdown`，从儿子节点更新当前节点也可以写一个专门的函数 `maintain`（或者对称地用 `pushup`），降低代码编写难度。 - 标记永久化，如果确定懒惰标记不会在中途被加到溢出（即超过了该类型数据所能表示的最大范围），那么就可以将标记永久化。标记永久化可以避免下传懒惰标记，只需在进行询问时把标记的影响加到答案当中，从而降低程序常数。具体如何处理与题目特性相关，需结合题目来写。这也是树套树和可持久化数据结构中会用到的一种技巧。 ## $5.0$ 训练指导 包括题目组成，例题说明，部分算法简析和一些其他的内容，可以帮助学习。 **题目组成：** - [P1204 \[USACO1.2\]挤牛奶Milking Cows](https://www.luogu.com.cn/problem/P1204) - [P1276 校门外的树（增强版）](https://www.luogu.com.cn/problem/P1276) - [P1904 天际线](https://www.luogu.com.cn/problem/P1904) - [P2003 \[CRCI2007-2008\] PLATFORME 平板](https://www.luogu.com.cn/problem/P2003) - [P1198 \[JSOI2008\]最大数](https://www.luogu.com.cn/problem/P1198) - [P1816 忠诚 ](https://www.luogu.com.cn/problem/P1816) - [P2357 守墓人](https://www.luogu.com.cn/problem/P2357) - [P2068 统计和 ](https://www.luogu.com.cn/problem/P2068) - [P2846 \[USACO08NOV\]Light Switching G](https://www.luogu.com.cn/problem/P2846) - [P3372 【模板】线段树 1](https://www.luogu.com.cn/problem/P3372) - [P3373 【模板】线段树 2](https://www.luogu.com.cn/problem/P3373) - [P1168 中位数](https://www.luogu.com.cn/problem/P1168) **部分题目解法简析：** - `P2003 [CRCI2007-2008] PLATFORME 平板`：观察题目，可以转化为区间修改，单点查询的问题，注意建树方法。 - `P1198 [JSOI2008]最大数`：单点修改，区间查询，可以考虑区间的特殊情况。 - `P2068 统计和`：几乎类似于模板，单点修改，区间查询。 - `P2846 [USACO08NOV]Light Switching G`：比较思维题，可以考虑异或结合线段树，区间修改查询。 - `P3372 【模板】线段树 1`：模板，区间修改，区间查询。 **例题说明：** 【模板】线段树，仅仅需要按照教程中建树，然后分类判断，进行更新和查询的操作即可。 **其他指导：** 部分题目不仅仅可以用线段树 AC，还可以用暴力或其他算法，建议仅使用线段树或者树状数组（bushi），这样可以锻炼自己读题和应用的能力，还能锻炼自己非模板题的 AC 能力。 ## $6.0$ 后话 如果你已经透彻地（或者说基本）理解这篇文章的内容，可以再浏览上述的参考资料，相信您会有更多收获的。 那么，以上就是线段树基础的学习笔记了，希望对大家有用。各位可以再评论区提出自己的疑惑或者不同意见，我会一一虚心听取，如果我才疏学浅不能解答我会去继续学习，如果是文章的学术性错误我会再看到的时候第一时间修正，如果是文章表述不够清楚或者是其他较小的问题，我会酌情解决。 …