数据结构：

1.栈:

单调栈：给定一个数组，对于该数组中的每一个元素，在数组左边或者右边找到第一个>=或者<=该元素的值；
例题：
1.[字串的最大差](http://oj.daimayuan.top/course/10/problem/436) 
2.[城市游戏](https://www.acwing.com/problem/content/154/)

for(int i=1;i<=n;++i){//stk[]存下标
	while(tt&&a[stk[tt]]>=a[i])--tt;//找到左边第一个大于我的元素
    l[i]=stk[tt],stk[++tt]=i;//倒着遍历时当tt=0时，l[i]=n+1
}

2.队列

单调队列：决策队列中一定不是最优解的集合，找到一个数组中的前k个元素中，单调递增或者递减序列
思路：  
1.遍历每一个元素，判断队头元素是否出队，出队则++hh;
2.模仿单调栈的形式，弹出与将入队的元素不满足单调性的元素
3.将该元素从队尾插入
此时，单调队列中的每一个元素都是在长度为k的原数组中时单调的

滑动窗口

最大子序和

for(int i=1;i<=n;++i){
	if(i-k+1>q[hh])++hh;
    while(hh<=tt&&a[q[tt]]>a[i])--tt;
    q[++tt]=i;
    /////////
}

3.Hash

1离散化：

get_hash(int x){
	if(!mp[x])return mp[x]=++idx;
    return mp[x];
}
字符串数组：O(n)预处理，O(1)查询；
void hash(){//自然溢出法
	p[0]=1,h[0]=1;
	for(int i=1;i<=n;++i){
    	p[i]=p[i-1]*seed;
    	h[i]=h[i-1]*seed+idx;//unsigned long long      seed通常为131  1331
    }
}
unsigned long long get(int l,int r){
	return h[r]-h[l-1]*p[r-l+1];
}

4.字符串

5.Tire(字典树)

6.堆

7.并查集

8.树状数组

9.线段树

懒标记：本区间已经被更新过了，但是子区间却没有被更新过，被更新的信息是什么
（区间求和只用记录有没有被访问过，而区间加减乘除等多种操作的问题则要记录进行的是哪一种操作）

当前节点已更新，而后续节点未更新

懒标记分为相对标记和绝对标记

10.ST表

11.点分治

12.Treap和Splay

13.LCA问题

1.树上倍增： DIS

1.树上倍增求LCA问题：O(nlog(n))预处理  O(log(n))查询
lg[i]=lg[i-1]+(1<<lg[i-1]==i)         lg[u]-------存每个点的深度的log值加1
f[u][k]=f[f[u][k-1]][k-1]             f[u][k]-----u结点的第2^k个父亲        
depth[u]=depth[fa]+1                  depth[u]----u结点的深度

void dfs(int u, int fa) {
fa[u][0] = fa; depth[u] = depth[fa] + 1;
for(int i = 1; i <= lg[depth[u]]; ++i)
    fa[u][i] = fa[fa[u][i-1]][i-1];
for(int i = h[u]; i; i = ne[i] )
	int j = e[i];
    if(j != fa) dfs(j , u);    
}

int LCA(int x, int y) {
if(depth[x] < depth[y]) swap(x, y);//找到最深的结点，从最深的结点开始向上跳
while(depth[x] > depth[y])
    x = fa[x][lg[depth[x]-depth[y]] - 1];//31，32行代码是为了让两个结点跳到同一高度
if(x == y) return x;
for(int k = lg[depth[x]] - 1; k >= 0; --k)//两个结点一块倍增往上跳。
    if(fa[x][k] != fa[y][k])
        x = fa[x][k], y = fa[y][k];
return fa[x][0];
}

14.欧拉定理和扩展欧拉定理

欧拉函数：φ(n) 表示小于等于 n 的正整数中与 n 互质的数的个数（欧拉函数）。
结论：a 与 m 互质时，a^φ(m) ≡ 1 (mod m)
扩展欧拉定理：b≥φ(m)时,a^b≡a^(b mod φ(m) + φ(m)) mod m

15.拉格朗日插值法

拉格朗日插值法模板题解