基本数据结构
栈
栈是一种遵循先进后出原则的数据结构,数据在同一端入栈和出栈。
手动实现如下:
1 | int stk[100005], top;//stk用于存放栈内的数据,top为栈顶,入栈和出栈都是在栈顶进行操作 |
是不是很简单呢?
C++的STL提供了stack给我们直接使用,它支持如下基本操作:
1 | stack<dataType>name;//创建一个元素类型为dataType的栈name |
单调栈
在栈的基础上,我们规定元素出栈的顺序必须是单调不降或单调不增的,对栈内元素的顺序没有要求。
对于单调不降的单调栈,入栈前把比要入栈的元素小的元素全部出栈。
对于单调不增的单调栈,入栈前把比要入栈的元素大的元素全部出栈。
1 | void ins(int x) { |
队列
队列是一种遵循先进先出原则的数据结构,数据在一端入队,在另一端出队。
手动实现如下
1 | int q[100005], head = 1, tail; |
C++的STL中同样提供了queue供我们使用,它支持如下基本操作:
1 | queue<dataType>name;//创建一个元素类型为dataType的队列name |
单调队列
与单调栈不同,单调队列要求队内的元素要是单调不降或单调不增的,且队首队尾都可以进行出队操作,只有队尾可以进行入队操作。
一般来说,单调队列会有一个限制的大小m,即最多只能有m个元素。
单调队列主要用于维护不同段区间内的最值,每次元素要入队时,与单调栈类似地,要让一些元素出队。
1 | void ins(int x) { |
链表
先鸽着
简单数据结构
ST表
ST表用于求静态区间最值,构建复杂度$O(n\log n)$,查询复杂度只有$O(1)$!
那么ST表是怎么实现的呢?显然区间[L,R]的最值可以拆成[L,L+x]与[R-x+1,R]的最值取最值,只要L+x>=R-x+1即可。
那么我们考虑求对于区间内每个位置i,从i开始往后$2^k$个元素中的最值ST[i][k],于是构建ST表的算法就出来了。
1 | //以求最大值为例 |
查询也好说:
1 | int query(int l, int r) { |
并查集
并查集用于维护集合的关系。
普通的并查集操作非常简单,直接上代码。
1 | //用fa[x]表示x所在的集合 |
不难看出,findf最多递归小常数次,因此并查集的复杂度是非常小的。
带权并查集(扩展并查集)
带权并查集即结点有权值的并查集,如果我们要维护元素之间可量化的属性,而且这种属性关系可以合并时,可以采用带权并查集。
带权并查集中每个元素的权值通常描述其与祖先的关系。
探究结点与祖先的关系我们可以利用向量偏移。
例题
首先我们确定属性,设sum[x]为从x到x的祖先的区间和
祭出好图
显然当roota!=rootb时,我们想要将roota和rootb合并,那么roota->rootb即sum[roota]是要更新的,可如何更新呢?
根据向量运算我们知道,(roota,rootb)=(b,rootb)-(b,roota)=(b,rootb)-(a,roota)+(a,b)
由此可得sum[roota]=sum[b]-sum[a]+w(a,b)
而当roota=rootb时,说明此时的区间通过前面的答案已经可以推出,只需要验证是否为真即可。
显然此时(a,b)=(a,root)-(b,root)
即s(a,b)=sum[a]-sum[b]
在找祖先的过程中,我们也需要对sum进行更新。
另外,我们推出的表达式是sum[r]-sum[l]的形式,因此左端点还要-1。
1 | int fa[N], sum[N]; |
可持久化并查集
咕咕咕
优先队列(二叉堆)
首先,优先队列并不是用队列实现的,一般我们用二叉堆来实现优先队列。
那么什么是优先队列?就是队列中的元素被赋予的优先级,当我们访问优先队列时优先访问优先级高的元素。
二叉堆,其实就是一棵二叉树,它满足父节点的优先级一定大于子节点的性质,换句话说,在二叉堆中,以任意节点x为根的子树中,x的优先级是最高的,这样的话,只要构建一个二叉堆,它的根节点就是优先级最高的点。
1 | //这里我们用一种比较方便的方法表示节点的左右孩子 |
手动实现起来相当麻烦,当然,C++的STL提供了priority_queue供我们直接使用,它支持以下基本操作:
1 | priority<dataType>pq; |
左偏树(可并堆)
有些时候,我们需要将堆进行合并,这时候就用到左偏树。
左偏树,左偏是啥意思?意思就是对于堆内任意一棵子树,其左子树中深度最小的叶子节点的深度要大于右子树中深度最小的叶子节点的深度,这样的话从整体上看,整棵树明显左边比较重。
具体实现:我们用并查集来维护不同的节点是否在同一个堆中,下面给出合并操作
1 | int merge(int x, int y) {//将y堆合并到x堆上,返回合并后的根节点 |
合并自然不用说,如果要删除根节点,只需要合并左右子树就行了。
v1.5.2