二维前缀和
//S[i,j]=第i行j列格子左上部分所有元素的和
//以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2,y2]-S[x1-1,y2]-S[x2,y1-1]+S[x1-1,y1-1];二维差分
//给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1,y1]+=c;
S[x2+1,y1]-=c;
S[x1,y2+1]-=c;
S[x2+1,y2+1]+=c;离散化
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(),alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(),alls.end()),alls.end());//去重复元素
//二分求出x对应的离散化的值
int find(int x){ //找到第一个大于等于x的位置
int l=0,r=alls.size()-1;
while(l<r){
int mid=l+r>>1;
if(alls[mid]>=x) r=mid;
else l=mid+1;
}
return r+1; // 映射到1, 2, ...n
}区间合并
// 将所有存在交集的区间合并
void merge(vector<PII> &segs){
vector<PII> res;
sort(segs.begin(),segs.end());
int st=-2e9,ed=-2e9;
for(auto seg:segs)
if(ed<seg.first){
if(st!=-2e9) res.push_back({st,ed});
st=seg.first,ed=seg.second;
}
else ed=max(ed,seg.second);
if(st!=-2e9) res.push_back({st,ed});
segs=res;
}并查集
(1)朴素并查集：
int fa[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点
int find(int x){
if (fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) fa[i] = i;
// 合并a和b所在的两个集合：
fa[find(a)] = find(b);
(2)维护size的并查集：
int fa[N], size[N];//fa[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
// 返回x的祖宗节点
int find(int x){
if (fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ){
fa[i] = i;
size[i] = 1;
}
// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
fa[find(a)] = find(b);
(3)维护到祖宗节点距离的并查集：
int fa[N], d[N];//fa[]存储每个点的祖宗节点, d[x]存储x到fa[x]的距离
// 返回x的祖宗节点
int find(int x){
if (fa[x] != x){
int u = find(fa[x]);
d[x] += d[fa[x]];
fa[x] = u;
}
return fa[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ){
fa[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合：
fa[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量Trie树
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
// 插入一个字符串
void insert(char *str){
int p = 0;
for (int i = 0; str[i]; i ++ ){
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++ ;
}
// 查询字符串出现的次数
int query(char *str){
int p = 0;
for (int i = 0; str[i]; i ++ ){
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}哈希表
(1) 拉链法
int h[N], e[N], ne[N], idx;
// 向哈希表中插入一个数
void insert(int x){
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}
// 在哈希表中查询某个数是否存在
bool find(int x){
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x) return true;
return false;
}
(2) 开放寻址法
int h[N];
//如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x){
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x){
t ++ ;
if (t == N) t = 0;
}
return t;
}字符串哈希
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ ){
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r){
return h[r] - h[l - 1] * p[r - l + 1];
}朴素版prim算法 时间复杂度 O(n2+m)，n表示点数，m表示边数
int n; // n表示点数
int g[N][N]; // 邻接矩阵，存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离
bool st[N]; // 存储每个点是否已经在生成树中
// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim(){
memset(dist, 0x3f, sizeof dist);
int res = 0;
for (int i = 0; i < n; i ++ ){
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if (i && dist[t] == INF) return INF;
if (i) res += dist[t];
st[t] = true;
for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
}
return res;
}Kruskal算法 时间复杂度 O(m*logm)，n表示点数，m表示边数
int n, m; // n是点数，m是边数
int p[N]; // 并查集的父节点数组
struct Edge{ // 存储边
int a, b, w;
bool operator< (const Edge &W)const{
return w < W.w;
}
}edges[M];
int find(int x){ // 并查集核心操作
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal(){
sort(edges, edges + m);
for (int i = 1; i <= n; i ++ ) p[i] = i;// 初始化并查集
int res = 0, cnt = 0;
for (int i = 0; i < m; i ++ ){
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b){// 如果两个连通块不连通，则将这两个连通块合并
p[a] = b;
res += w;
cnt ++ ;
}
}
if (cnt < n - 1) return INF;
return res;
}染色法判别二分图 时间复杂度 O(n+m)，n表示点数，m表示边数
int n; // n表示点数
int h[N], e[M], ne[M], idx; // 邻接表存储图
int color[N];// 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色
// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c){
color[u] = c;
for (int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if (color[j] == -1){
if (!dfs(j, !c)) return false;
}
else if (color[j] == c) return false;
}
return true;
}
bool check(){
memset(color, -1, sizeof color);
bool flag = true;
for (int i = 1; i <= n; i ++ )
if (color[i] == -1)
if (!dfs(i, 0)){
flag = false;
break;
}
return flag;
}匈牙利算法 时间复杂度 O(nm)，n表示点数，m表示边数
int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];//存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过
bool find(int x){
for (int i = h[x]; i != -1; i = ne[i]){
int j = e[i];
if (!st[j]){
st[j] = true;
if (match[j] == 0 || find(match[j])){
match[j] = x;
return true;
}
}
}
return false;
}
// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ ){
memset(st, false, sizeof st);
if (find(i)) res ++ ;
}KMP 字符串匹配
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
//求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ ){
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; i ++ ){
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m){
j = ne[j];
// 匹配成功后的逻辑
}
}