Day4 基础数据结构

零、数据结构

（一）什么是数据结构

百度百科：数据结构是计算机储存、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

比如我们学过的数组，就是一种简单的数据结构，一维数组对应顺序表，即每个元素有对应的下标，可以通过元素的地址快速找到对应下标的元素。

（二）常用的数据结构

数组(Array)，栈(Stack)，队列(Queue)，链表(Linked List)，树(Tree)，图(Graph)，堆(Heap)，散列表(Hash)。

一、栈(Stack)

（一）什么是栈

百度百科：栈(stack)是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表，这一段被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

通俗的讲，栈就是后进先出的结构。

（二）栈的实现

我们一般用一个指针top记录栈顶的位置，进栈即stack[++top]=x，出栈即a=x,top--.

具体代码我们结合题目去看。

（三）栈的实例

1.单调栈

（1）定义：

单调栈即栈内元素有序的栈，又分为单调递增栈和单调递减栈。

单调递增 / 减栈：从栈顶到栈底元素是从小到大 / 从大到小。

（2）实现方法：

以单调递增栈举例，即推进元素时比较栈顶元素与待推入元素的大小，若栈顶元素比待推入元素大，则推入；否则弹出栈顶元素，直至栈顶元素比待推入元素大或栈空，再推入。（例：5,2,3,1,4）

（3）例1：单调栈模板题：luoguP5788传送门

题目大意：输出一串数列中每个元素之后第一个大于该元素的元素下标。

解题思路：维护一个单调递增栈（对应维护一个下标栈），推入元素前弹出所有比推入元素小的元素，同时这些弹出元素对应的答案值为推入元素的下标（推入弹出同时对于下标使用）。

实例代码：

2.前中后缀表达式

（1）定义：

前缀表达式，即波兰式，是一种运算符在前，操作数在后的表达式。如-1+23。

中缀表达式，即常见的算术表示式。如1-(2+3)。

后缀表达式，即逆波兰式，是一种运算符在后，操作数在前的表达式。如123+-。

易知，前缀和后缀表达式是不需要括号的，且更容易被计算机这种按照读入顺序进行计算的方式识别。

（2）实现方法：

①求后缀表达式的值

维护一个栈，从左向右读入该后缀表达式，并执行以下操作：

若读入操作数，则压入栈；

若读入操作符，则弹出栈顶两个元素并执行该操作符的运算，结果再压回栈。

读完整个表达式后，栈中元素即为答案。

②中缀转后缀

维护一个栈，从左向右读入该中缀表达式，并执行以下操作：

若读入操作数，则直接输出；

若读入运算符，则判断：

Ⅰ当遇到左括号或者栈为空时，直接压栈。

Ⅱ当遇到右括号时，依次弹栈并输出，直至栈顶为左括号，将左括号弹出。

Ⅲ当遇到操作符时：若栈顶为左括号，则直接压栈、

​ 若栈顶是操作符，则比较两个操作符的优先级，若当前字符优先级高，则压栈，否则将栈 顶运算符弹出并输出，直至当前字符优先级高或是遇到左括号或是栈为空，再压栈。

遍历完整个表达式后，弹栈并输出。

在洛谷上看到一个流程图版，放在这里供参考，侵删（cr.qinyubo）

（3）例2：后缀表达式：luoguP1449传送门

题目大意：一个后缀表达式以@结束，其中操作数以.结束，求该后缀表达式的值。

解题思路：参见上面求后缀表达式的值，其中操作数需要考虑多位数的情况。

实例代码：

例3：表达式的转换：luoguP1175：传送门

题目大意：给定一个中缀表达式，其中包括0123456789+-*/^()，表达式中数字都是一位的，要求输出转化后的后缀表达式及后缀表达式计算结果的每一步。

解题思路：按照上面讲的中缀转后缀的方法，将给定的中缀表达式转换为后缀表达式，再参照上面讲的后缀表达式求值的方法求解即可。

实例代码：

二、队列(Queue)

（一）什么是队列

百度百科：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

通俗的讲，队列就是先进先出的结构。

（二）队列的实现

我们一般用两个指针front、rear分别记录队头、队尾的位置，进队列即queue[++rear]=x，出队列即a=x,front++.具体代码我们结合题目去看。

特别地，为了节省空间，有时也会用到循环队列。我们易知从队头弹出元素后，队头之前的空间便不能再用了。循环队列可以弥补这一缺点，即当rear指针指到队列空间末尾时，让其重新等于0，即重新利用之前的空间。具体实现方法在这里不做赘述，大家可以自行了解。

（三）队列的实例

1.单调队列

（1）定义：

单调队列，即单调递减或单调递增的队列（废话）。

单调递减 / 增队列：从队头到队尾元素是从大到小 / 从小到大。

单调队列是一个双端队列，即从队尾入列，但可以从队首或队尾出列。

双端队列(deque)可以看做是同时具有队列和栈性质的数据结构（大概）。

（2）例4：滑动窗口（单调队列模板题）：luoguP1886传送门

题目大意：有一个长为n的序列，以及一个长为k的窗口。现在这个窗口从左向右滑动，每滑动一个单位，输出窗口内的最大值和最小值。

解题思路：首先求最小值，维护一个单调递增队列，存储的是元素下标，队首即为最小值元素的下标，注意判断当前元素是否在窗口内。求最大值同理。

实例代码：

2.BFS

（1）定义

BFS(Breadth First Search)，广度优先搜索。与之对应的是DFS(Depth First Search)，深度优先搜索。

先来说一下深搜。深度优先搜索遵循尽可能“深”的搜索。它的基本思想是：为了获得解，先选择某一种情况向下（子节点）搜索。在搜索过程中，一旦发现与原来的选择或规定不符，就回溯至父节点重新选择另一种情况，如此反复，直至求的最优解。深搜一般用递归或栈来实现。

与深搜不同，广搜则是一种盲目的搜寻法。它的基本思想是：为了获得解，系统地展开并检查图中所有节点，直至寻找到解。广搜一般用队列实现。

放到树上举例子，DFS更像是中序遍历，而BFS更像是层序遍历。

（2）BFS的实现

以一张图距离，BFS会从一个节点开始，遍历该节点的每条出边，将到达的节点推入一个队列。遍历完所有出边后，从队首取出一个节点，再遍历这个节点的所有出边，以此类推，直至遍历结束或找到答案。

（3）浅谈DFS与BFS的区别

简单来说，广搜适用于找单一的最短路，它的特点为“搜到就是最优解”；而深搜适用于找所有解的问题。

BFS：对于解决最短或最少问题特别有效，而且寻找深度小，但缺点是内存耗费量大（需要开大量的数组来储存状态，即队列）。

DFS：对于解决遍历和求所有解问题有效，对于问题搜索深度小的时候处理速度迅速，然而在深度很大的情况下效率不高。

（4）例5：填涂颜色：luoguP1162传送门

题目大意：一个由0构成的地图，里面有一个被1围成的圈，让你把圈内的0填成2。

解题思路：我们把圈外的0填成2，然后输出的时候输出2-a[i][j]即可。填2即用到了BFS，BFS即用到了队列。

实例代码：

三、线段树

（一）什么是树

由n-1条边连接n个结点即为树。（草率而不严谨的定义）

树上通常有：儿子，父亲等通俗易懂的名词；入度，出度等需要知道的名词。

二叉树即每个节点都只有左儿子和右儿子两个儿子的树。

二叉树的特性使之应用极广。

二叉树中，满二叉树和完全二叉树又是值得拎出来说的。

满二叉树即每个结点都有0或2个子结点，导致整棵树的第i层都是2^{i-1}个结点。

完全二叉树即在满二叉树的基础上，最后一行从右向左删去若干个结点构成的。

（二）二叉树的存储结构

二叉树有很多存储方式，就像数据结构本身就有很多存储方式一样。

我们这里只介绍一种存储结构，也是我们后期线段树用到的存储结构，即层序存储。

一棵二叉树，可以补全为一棵满二叉树。一棵满二叉树按照层序编号，即可将每个结点信息进行存储。

这种存储方式的好处是，我们可以快速的找到一个结点的父亲和两个儿子。比如第i号结点，它的父亲即为a[i/2]，它的左儿子为a[i*2]，右儿子为a[i*2]+1。

（三）线段树

讲完先修知识后，我们来看看什么是线段树。

线段树，可以通俗的理解为由线段构成的树或者把线段分成树。

我们先来看一个实例。

我们可以看到，将线段[1,10]做成线段树，即二分线段作为左右儿子，以此类推。

线段树的用处是，对编号连续的一些点进行修改或者统计操作，复杂度都是O(log2(n))

线段树的原理是，对每个区间的修改可以分解为对若干个子区间的修改，如对[3,8]这个区间进行修改，只需要对[3,3],[4,5],[6,8]这三个点进行修改即可，区间求和同理。具体实现我们慢慢来讲。

由此看出，用线段树统计的东西，必须符合区间加法，否则，不可能通过分成子区间来得到结果。

（四）线段树的实现原理

线段树有很多操作，如单点修改，区间修改，单点查询，区间查询等，我们挨个说。

线段树一般会维护区间内的一个内容，如区间和，最大值，最小值等等。

以下内容由上图即[1,10]举例。

1.线段树的单点修改

单点修改是很简单的，简单的像单点查询一样。

假设我们要修改[5,5]的值，我们只需要修改[5,5],[4,5],[1,5],[1,10]即可。时间复杂度为O(log2(n))

2.线段树的单点查询

单点查询是很简单的，简单的像单点修改一样。

假设我们要查询[5,5]的值，我们可以直接访问该结点即可。至于结点序号，有了n就能推出来了。就算推不出来，还可以通过[1,10]→[1,5]→[4,5]→[5,5]来逐步找到该结点。时间复杂度为O(log2(n))

3.线段树的区间查询

区间查询，即可将要查询的区间分成若干个区间，然后将这些区间的信息合并即为要查询的信息。就如上文所提到的，如果我们要查询[3,8]这个区间，就可以将[3,3],[4,5],[6,8]三个区间的信息合并得到。

这里引入一个定理：当n≥3时，一个[1,n]的线段树可以将[1,n]的任意子区间[L,R]分解为不超过2\lfloor log_2 (n-1)\rfloor个子区间。因此区间查询的时间复杂度为O(log2(n))。定理证明

4.线段树的区间修改

与区间查询类似，区间修改也是将区间分成若干子区间操作的。

与区间查询不同的是，在区间修改时我们引入了lazy标记，即懒惰标记，也叫延迟标记。

标记的用处是：标明本节点的信息已经根据标记更新过了，但子结点及子树仍需要更新

举个例子，假设我们要给[3,8]这个区间内每个值都加1，那么实际上，只改变[3,3],[4,5],[6,8]这三个结点，而它们的子树还没有变。我们在这三个结点处打上lazy标记，对于[6,8]这个结点，我们要加3(即678)。这样向下的修改就被我们延迟下来了。但是向上显示的信息却是修改后的结果，比如我们要查询[6,10]，是由[6,8],[8,10]两个区间组成，其中[6,8]的值已经变了，因此保证我们查询的是正确结果。当我们需要查询子树的信息时，再将lazy标记下推即可。

标记有相对标记和绝对标记之分：

绝对标记如将区间所有数+x，标记间可以共存，和打标记的顺序无关。因此我们可以区间修改时不下推标记，等到查询时再下推。

绝对标记如将区间内所有数变成x，打标记的顺序会直接影响结果，所以这种标记在区间修改时必须下推旧标记，否则会出错。

值得注意的是，有多个标记时，标记下推的顺序也很重要，错误的下推顺序可能会导致错误。

（五）线段树的递归实现

例6：[模板]线段树2：luoguP3373：传送门

题目大意：一个数列，区间修改，区间查询。其中区间修改有区间乘和区间加两种。

解题思路：我们构造一棵线段树，维护每个区间的sum值，然后设两个lazy标记，一个叫add代表加法lazy标记，一个叫mu代表乘法lazy标记。

先放个整体代码，然后我们分块去讲每个函数的含义。

0.定义

这里我们定义一个结构体表示这棵树。

其中t[i]表示第i号结点。具体结点编号请参考上面二叉树的存储结构。

每个结点内包含五个量，其中，l表示该结点所表示区间的左端点，r表示该结点所表示区间的右端点，sum表示该结点表示区间的和，mu表示该结点的乘法lazy标记，add表示该结点的加法lazy标记。

1.建树（初始化）

这个函数就是用来建树的。

函数有三个形参，其中x代表第x号结点，l表示结点的左编号，r表示结点的右编号。

然后我们把x结点的左右区间赋成l和r，将mu标记初始化为1（很好理解，就像你要求几个数的乘积，初始的sum一定等于1）。

然后，如果l==r，说明我们已经推到一个点了，那么这个点的sum值就等于a数组对应的值。

如果l!=r，我们就递推下面的区间（用二分），最后这个点的sum值等于它左右儿子sum值的和。

2.下传标记（spread函数）

下传标记是线段树区间修改中最重要的操作。

下传标记时，本结点的mu和add标记会影响儿子结点的sum值、mu和add标记。

具体的下传参考代码。

下传完毕后，要记得将本结点的标记清空。

3.区间修改

本题区间修改涉及两种操作，分别是区间乘和区间加。

两者在递推的时候，操作都是一样的：先推标记，再逐步向下递推，最后修改本结点的sum值。

(t[x].l >= l && t[x].r <= r)判断的是该结点的区间是否在大区间内，如果是，则：

区间加很简单，修改本结点的add标记和sum值。

区间乘也很简单，修改本结点的mu标记、add标记和sum值即可。

4.区间查询

区间查询直接查找大区间分成的若干个子区间的sum值，加和即可。

在区间加和区间乘混合时，我们一定要注意乘法的优先级，然后在算法中体现。

下面给一个只有区间加的代码，题目是[模板]线段树1：luoguP3372：传送门，大家结合代码自行理解。

四、树状数组

（一）树状数组简介

树状数组，就是用数组模拟树。

树状数组也用来解决区间上更新和求和的问题。

我们已经学习过线段树了，上述问题线段树也能解决，那么为什么还要学习树状数组呢？

原因有二：一，树状数组的常数小，时间复杂度上如果线段树被卡常就可以考虑树状数组（一般碰不到有人卡线段树的常但是以防脑残出题人）。二，树状数组比线段树稍微好写一些（划重点，好写不等于好理解）。

举个不恰当的例子，我们都知道用字符串可以模拟大数运算，但是没有人会在1+1这种问题上进行字符串模拟（很不恰当，大概理解就好）。

（二）树状数组是什么

我们先来看一个树状数组：

我们学过用二叉树的方式解决区间问题，即线段树。

那么树状数组可以看成是在二叉树中删除若干个结点组成。

换句话说一个树状数组可以恢复出一棵二叉树。

在这个树状数组中：

c[1]=a[1];

c[2]=a[1]+a[2];

c[3]=a[3];

c[4]=a[1]+a[2]+a[3]+a[4];

c[5]=a[5];

c[6]=a[5]+a[6];

c[7]=a[7];

c[8]=a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8];

……

由此我们可以发现，c[i]=a[i-2^k+1]+a[i-2^k+2]+……a[i]，其中k是i的二进制中最低位到最高位连续零的个数，也是i的二进制中最低位1的位权。

举个例子，十进制下的4即二进制下的100，所以c[4]=a[4-2^2+1]+a[4-2^2+2]+a[4-2^2+3]+a[4]

这样存储我们该怎么求和呢？

举个例子，假设我们要求前7个数的和，那么sum_7=c[7]+c[6]+c[4]

所以我们又发现，sum_i=c[i]+c[i-2^{k1}]+c[(i-2^{k1})-2^{k2}]+···，其中2^{k1}为i的二进制中最低位1的位权，2^{k2}为i的二进制中第二低位1的位权，即(i-2^{k1})的二进制中最低位1的位权。

即sum_7=c[(111)_2]+c[(110)_2]+c[(100)_2]=c[(111)_2]+c[(111)_2-2^0]+c[((111)_2-2^0)-2^1]

综上我们发现，树状数组是对二进制的灵活运用。

我们还发现，树状数组对最低位1有着灵活的应用，那么我们该怎么找这个最低位1以及他的位权呢？

其实，我们只需要得到最后一个1的位置，并且把除了这个位置以外的所有位置置成0即可。

所以我们有了第一种算法：2^k=x&(x^(x-1))：

我们用二进制下的0110即十进制下的6举个例子

(0110)_2-1=(0101)_2，在这一步中，我们达成了这个数的最后一个1开始到最后所有数都取反

(0110)_2^(0101)_2=(0011)_2，在这一步中，我们达成了最末位1之前的所有数都是0，后面（包括这个1）都是1

(0110)_2&(0011)_2=(0010)_2，在这一步中，我们达成了最末位1之前的所有数都是0，而最后一个1之后的所有数也都是0，只有这个1的位置是1，我们便得到答案了。

这个算法的灵性在于怎么灵活的运用位运算分别将之前和之后的所有位置置成0。

这样我们就找到了6的二进制中最低位1的位权即2.

另一种算法是：前人的智慧告诉我们，2^k=i&(-i)，那么这个算法的原理何在呢？

(三)lowbit

$2^k=$i&(-i)

1.原码，反码和补码

我们首先来看二进制的相关知识：原码，反码和补码

我们首先知道正数的原码，反码和补码都一样

然后来看负数，我们给出一个8位二进制负数(10101011)_2，

反码就是在原码的基础上，符号位不变，其余各位取反：原码[10101011]=反码[11010100]

补码就是在反码的基础上按照正常的加法运算+1：原码[10101011]=反码[11010100]=补码[11010101]

PS：反码和补码的引入是为了方便计算机计算的，感兴趣可以自己了解

2.lowbit

负数的存储特性是：负数是以补码存储的。

那么我们来看x&(-x):

还用二进制下的的0110即十进制下的6来举例子，那二进制下的1110即十进制下的-6，（这里是4位二进制）

我们刨除符号位来看剩余部分，因为负数按补码形式存储，我们来看原码[110]=补码[010]

然后(110)&(010)=(010)，就找到最末位1了，很神奇。

原理在于：补码的性质是原码取反+1，我们关注最末位1和它的前后，原码取反后+1，使得最末位1变为1，后面所有数变为0，然后x&x的补码，就有最末位1之前的所有数都是0（与运算和取反运算结合），而最后一个1之后的所有数也都是0（补码的最末位1后面所有数都是0，然后与运算），只有这个1的位置是1（原码和补码的这一位都是1），最后符号位进行与运算后保证是正数。再举例(43)_{10}=(00101011)_2

(四)树状数组的实现原理

树状数组的实现一般也是：单点修改，单点查询，区间修改，区间查询。

以下内容由上图即16个数据的树状数组举例。

1.单点修改

比如我们要修改a[5]的值，只需要修改c[5],c[6],c[8],c[16]。

怎么算呢+只需要递推修改x，每次加上lowbit(x)即可。

即a[i]包含于c[i+2^{k1}]，c[(i+2^{k1})+2^{k2}]···

2.查询

大家看到小标题写的是查询而不是单点查询/区间查询，为什么呢？

这是因为，在树状数组中，我们是没有办法维护区间和的，所以想要求区间和怎么办呢？

我们维护前缀和，然后用y的前缀和-(x-1)的前缀和就是区间[x,y]的和了。

所以，我们在树状数组中一般维护的都是前缀性的东西。

所以这里我们来看例7：[模板]树状数组1：P3374传送门

题目大意：单点修改，区间查询

实例代码：

3.区间修改

如果题目让你把[x,y]区间内的所有值全部加或减k，那么怎么操作呢？

对于树状数组，我们好像只能将x,x+1,…,y每一个值都单独修改一遍，但是这样做复杂度一定很难受。

所以我们要换一种思路，即不能用原有数据维护前缀和建树。

那么我们引入差分。

（1）什么是差分

如果有b[1]=a[1]，b[j]=a[j]-a[j-1]，则a[j]=b[j]+b[j-1]+…+b[1]。

即a[i]=\sum_{j=1}^{i}d[j]。

例如：

原始数组a	9	3	6	2	6	8
差分数组b	9	-6	3	-4	4	2

a[4]=b[4]+b[3]+b[2]+b[1]=2。

然后给定一个任务：把区间[l,r]所有数加上k。（假设是[2,4]）

加k后数组a	9	5	8	4	6	8
差分数组b	9	-4	3	-4	2	2

我们发现，差分数组b中只有b[2]和b[5]的值改变了。

原理手推一下就很好理解。

所以利用差分数组解决区间修改的问题，就可以得出公式：b[l]+=k,b[j+1]-=k。

（2）利用差分进行区间修改

我们用树状数组维护前i项差值和，即tree[i]=\sum_{j=1}^id[j]，其中d[j]=a[j]-a[i]。

区间修改时只需要修改t[l]和t[r+1]即可。

利用这个原理我们还可以在维护差分数组前缀和时进行区间查询。

（3）利用差分进行区间查询

由上面\sum_{i=1}^{n}a[i]=\sum_{i=1}^{n}\sum_{j=1}^{i}d[j]，我们可以推导

a[1]+a[2]+…+a[n]，

=(d[1])+(d[1]+d[2])+…+(d[1]+d[2]+…d[n])，

=n×d[1]+(n-1)×d[2]+…+d[n]，

，=n×(d[1]+d[2]+…d[n])-(0×d[1]+1×d[2]+…+(n-1)×d[n])，

即\sum_{i=1}^{n}a[i]=n×\sum_{i=1}^{n}d[i]-\sum_{i=1}^{n}(d[i]×(i-1))。

所以我们维护tree1[i]=\sum_{i=1}^{n}d[i]，tree2[i]=\sum_{i=1}^{n}(d[i]×(i-1))即可。

例8：[模板]树状数组2：P3368传送门

题目大意：区间修改，单点查询

实例代码：