数据结构专题
数据结构
STL
vector
在数组中访问复杂度为O（1）；
关于链表，他可能可以实现动态数组，但访问复杂度为O（n）
当空间不够 vector会自动给你定义两倍到三倍的位置
定义方式：vector<int> a;
在末尾压入容器：a.push_back(x);
在末尾弹出容器：a.pop_back();
清空容器：a.clear();
查询元素个数：a.size();
首指针：a.begin();
插入元素在sit位置：a.insert(sit,x);
其中sit是vector的迭代器。
其它像数组一样调用就可以了。
看做是一个动态数组
STACK(栈)
定义：stack<int> a;
查询栈顶：a.top();
压入栈顶：a.push(x);
将元素从栈顶弹出：a.pop();
查询a中的元素个数：a.size();
但是，清空只能慢慢pop。
需要注意的是，当没有元素时，top会返回
queue
定义：queue <int> a;
插入队尾：a.push(x);
删除队首：a.pop();
查询队尾：a.back();
查询队首：a.front();
查询长度：a.size();
清空只能慢慢pop。
add
如何用两个栈模拟队列（先入先出）
入队：压入栈A；
出队： 如果栈B中没有元素，那么将A中的所有元素压入B，那么A的栈底就变成了B的栈顶，弹出B栈顶
如果B中有元素，直接弹出B栈顶
正题
二叉搜索树
特殊的二叉树
满足以下性质：
设 x 为二叉查找树中的一个节点。
如果 y 是 x 的左子树的一个节点，则 key[y] <= key[x].
如果 y 是 x 的右子树的一个节点，则 key[x] <= key[y].
我们已经知道，二叉查找树上的各基本操作的运行时间都是O(h)，h 为树的高度。
但是随着元素的插入或删除，树的高度会发生变化。
例如，如果各元素按严格增长的顺序插入，那么构造出的树就是一个高度为 n - 1 的链。
如果各元素按照随机的顺序插入，则构造出的二叉查找树的期望高度为 O(log n)。
这里省略证明，但这是一个重要的结论。
当看见题目中出现“数据是随机构造的”时，要能够记起这个结论哦！
二叉堆（HEAP）（图太多了贴不过来，看网盘的课件吧）
小根堆：
最小堆是一个关键码序列{K1,K2,…,Kn}，它具有如下特性：
K[i] <= K[2i]
K[i] <= K[2i+1]
大根堆类似；
从逻辑上看，堆是一种树状结构；
pop：删除根节点；
递归补上较小的子节点；
push：放到树叶上，从下到上依次交换它与它的父节点的位置，直到父节点比他小；
例：1有序表的最小和：
A[1] + B[1] < = A[1] + B[2] <= … <= A[1] + B[n] >
A[2] + B[1] <= A[2] + B[2] <= … <= A[2] + B[n]
………
A[n] + B[1] <= A[n] + B[2] <= … <= A[n] + B[n]；在这个表格中同一列的上面小，同一行中左面小
所以我们不妨建一个堆，把所有第一列的数（共n个）加入堆中
然后从堆中取出根（最小），cnt++，并将根在上表中右侧的一个值加入堆，以此类推
2.丑数
将1,3,5,7加入优先队列，再将它们的倍数依次加入优先队列，第k个出队的即为所求
线段树
（PS:HYF大佬说luogu日报有一篇非常好的介绍但我没有找到）
但我发现了3000+点赞的神级题解：神仙题解
他可以将任何一个长度为L的线段分成不超过2logL条不同的线段
这种数据结构需要自己写
要牢牢掌握
线段修改：用LAZY TAG（懒标记，延迟修改）
先打一个标记，在以后访问时顺便把标记带下去即可。
线段树可以做更多更强的事：
1.把线段上所有的值都+v，只需要把=v改成+=v
2.求线段最小值：Min=[x]=min(Min[ls],Min[rs])即可，当这个线段所有数都加v时，Min[x]+=tag[x]；
3.只要是分治能做好的事，线段树也能做好
P1115 最大子串和
这个问题没有那么复杂，他是一个贪心的经典问题
从x往右搜，如果a1>0那么将a1加入子串，如果a1+a2>0,a2也加入，否则a1阿都不要了……
很简单对吧
SPOJ GSS1
似乎跟上边那个差不多
线段树更优；
引用课件：
为了更新 lmax 和 rmax，我们还需要记录每个区间的区间和 sum。
这样就有：
lmax[x] = max(lmax[ls], sum[ls] + lmax[rs])
rmax[x] = max(rmax[rs], sum[rs] + rmax[ls])
void update(int x){
smax[x] = max(max(smax[ls], smax[rs]), rmax[ls] + lmax[rs]);
lmax[x] = max(lmax[ls], sum[ls] + lmax[rs]);
rmax[x] = max(rmax[rs], sum[rs] + rmax[ls]);
sum[x] = sum[ls] + sum[rs];
}
void build(int l, int r, int x){
if (l == r){
smax[x] = lmax[x] = rmax[x] = sum[x] = a[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, ls);
build(mid + 1, r, rs);
update(x);
}
void query(int A, int B, int l, int r, int x, int &Smax,
int &Lmax, int &Rmax, int &Sum){
if (A <= l && r <= B){
Smax = smax[x];
Lmax = lmax[x];
Rmax = rmax[x];
Sum = sum[x];
return;
}
void query(int A, int B, int l, int r, int x, int &Smax, int &Lmax, int &Rmax, int &Sum){
if (A <= l && r <= B){
…
}
int mid = (l + r) >> 1;
int smaxl = -1e9, lmaxl = -1e9, rmaxl = -1e9, suml = 0;
int smaxr = -1e9, lmaxr = -1e9, rmaxr = -1e9, sumr = 0;
if (A <= mid) query(A, B, l, mid, ls, smaxl, lmaxl, rmaxl, suml);
if (mid < B) query(A, B, mid + 1, r, rs, smaxr, lmaxr, rmaxr, sumr);
Lmax = max(lmaxl, suml + lmaxr);
Rmax = max(rmaxr, sumr + rmaxl);
Smax = max(max(smaxl, smaxr), rmaxl + lmaxr);
Sum = suml + sumr;
}能看懂多少看多少吧
前缀后缀。。。。
SPOJ GSS3
加了一个单点修改，yiyang
SPOJ GSS5
这次与以往不同的是，限定了左右端点的范围。
那么需要进行一下分类讨论。
如果 [x1, y1] 和 [x2, y2] 没有交集，即 x2>y1
答案显然等于: Rmax([x1, y1]) + Sum(y1 + 1, x2 - 1) + Lmax([x2, y2])
如果 [x1, y1] 和 [x2, y2] 有交集，即 y1 >= x2
这个时候，区间分为三个部分：
[x1, x2 - 1], [x2, y1], [y1 + 1 .. y2]
左端点有两种选择，右端点也有两种选择，一共四种情况。
进一步讨论，变为三种情况：
Smax([x2, y1])
Rmax([x1, x2 - 1]) + Lmax([x2, y2])
Rmax([x1, y1]) + Lmax([y1 + 1 .. y2])转化为GSS1即可
POJ 3321
利用dfs序
一个子树对应了一个dfs的区间，想想发现很对（可以自己画画图康康）
就可以和线段树一样操作了
HDU 3333 图灵树
LCA
求两个节点的最近公共祖先
法一：暴力求解。
从两个点依次往上枚举祖先到根节点，染色，找到公共祖先
法二：倍增算法
记up[u][k]为u节点向上走2^k步到的节点
up[u][0]=fa[u]
up[u][1]=fa[fa[u]]
可以找到这个递推关系式：O(logn)
up[u][1]=up[up[u][0]][0]
up[u][2]=up[up[u][1]][1]
up[u][k]=up[up[u][k-1]][k-1]
做法：如果u，v不在同一层，先通过up数组让v的祖先与u在同一层
比如deep【u】-11=deep【v】
那么11=8+2+1 (有点像快速幂)
接下来，在同一层的这两个节点
有一点：最近公共祖先的祖先一定是公共祖先
将k从一个较大的数（这时已经跳过了）n-1枚举
直到up不相同，将u，v……
看课件，代码
RMQ问题
ST 算法
令f[i][k]表示[i,i+2^k-1]中的最小值
那么f[i][k + 1] = min(f[i][k], f[i + (1 << k)][k])
查询时给了一个区间[l, r]，我们找一个最大的j满足2j <= r - l + 1 >
于是我们可以用f[l][j]和f[r – 2j + 1][j]来覆盖这个区间，
得到最小值
也即answer = min(f[l][j], f[r – (1 << j) + 1][j])
树状数组
跟线段树差不多的一个东西
二维前缀和
a[i][j]前缀和即为他左上方所有数的和（共i*j个数）
递推公式(容斥原理)：
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j](画个图就会发现他是对的）
思维：（dalao随意，窝背代码）
emmmmm~
例题四 CF 961E
x<y<=A[x]且A[y]>=x
排序，由大到小枚举x，如果A[y]>=x,在y的bool数组上打一个标记，最后扫一遍x到A[x]，加上标记的个数
MAP
HASH思想
我要用a[1010000100100101010]但是会爆空间
那么就可以将这个数映射到另一个数
比如x=x%p
但是如果有两个同余的x怎么办
把x%p的位置挂链表，把后来的放到链表里
另一种方法，当这个位置有数了，就放在下一个位置，查找的时候也不断往下一位找，直到找到正确的
字符串哈希
比较字符串
算出每个字符串的哈希值（比如131进制的数%一个质数）
set（集合）
他是一个很强的平衡树
平衡树
通过旋转的方法让长度为n的单链变为高度为logn的二叉查找树
模板：
struct treap {
#define N 700010
int ch[N][2],w[N],s[N],p[N],rt,cnt;
#define lc ch[x][0]
#define rc ch[x][1]
void rotate(int& x,int d) {
int k=ch[x][d^1]; ch[x][d^1]=ch[k][d]; ch[k][d]=x;
pushup(x); pushup(k); x=k;
}void ins(int& x,int k) {
if(!x){x=cnt++; w[x]=k; p[x]=rand();
lc=rc=0; s[x]=1;
}else{
int d=k<w[x],&u=ch[x][d];
ins(u,k); if(p[u]>p[x]) rotate(x,d^1);
pushup(x);
}
}void del(int& x,int k) {
if(w[x]==k){
if(!lc)x=rc;
else if(!rc)x=lc;
else{
int d=p[lc]>p[rc];
rotate(x,d); del(ch[x][d],k);
}
}else{
int d=k<w[x]; del(ch[x][d],k);
}pushup(x);
}int rank(int x,int k) {
if(!x)return 0;
if(k<=w[x])return rank(rc,k);
if(k>w[x])return rank(lc,k)+s[rc]+1;
}int kth(int x,int k) {
int d=k-s[rc];
if(d==1)return w[x];
if(d>1)return kth(lc,d-1);
else return kth(rc,k);
}void init(){s[0]=0;rt=0; cnt=1;
}inline int pushup(int x) {if(x)s[x]=s[lc]+s[rc]+1; }
int pred(int x,int y,int k) {
if(!x)return w[y];
if(w[x]<=k) return pred(lc,y,k);
else return pred(rc,x,k);
}int succ(int x,int y,int k) {
if(!x)return w[y];
if(w[x]>=k)return succ(rc,y,k);
else return succ(lc,x,k);
}
}