数据结构与算法分析（to be continued...）

前导
表、栈和队列
树、二叉树、平衡树
散列、排序、不相交集
堆、图论算法

数学知识复习

$N\mid(A-B)\rightarrow A\equiv B\pmod N$
$A\equiv B\pmod N\rightarrow A+C\equiv B+C\pmod N$
$A\equiv B\pmod N\rightarrow AD\equiv BD\pmod N$
$\gcd(a, b)=\gcd(b, a\bmod b)$
$M>N\rightarrow M\bmod N<M / 2$

// 2^3 === 2^(011)
int qPow(int a, int n){
    int res = 1;
    while(n){
        if(n & 1)
            res *= a;
        a *= a;
        n >>= 1;
    }
    return res;
}

// a >= b
int gcd(int a, int b){
    if(a % b == 0)
        return b;
    return gcd(b, a % b);
}

int gcd(int a, int b){
    while(b){
        a %= b;
        swap(a, b);
    }
    return a;
}

表、栈和队列

为避免插入和删除的线性开销，我们需要允许表可以不连续存储，链表便由此而生。

struct List{
    int val;
    List* next;
    List(int x) : val(x), next(nullptr) {}
};

List* reverse(List* head){
    if(head == nullptr || head->next == nullptr)
        return head;
    List* root = reverse(head->next);
    head->next->next = head;
    head->next = nullptr;
    return root;
}

基于链表可实现基数排序（radix sort），属于桶排序的推广形式。

input: 0 -> 1 -> 512 -> 343 -> 64 -> 125
sort_1: 0 -> 1 -> 512 -> 125 -> 343 -> 64
sort_2: 0 -> 1 -> 64 -> 125 -> 343 -> 512

栈（stack）：FILO；队列（queue）：FIFO

stack<int> s	queue<int> q
s.push(1)	q.push(1)
s.pop()	q.pop()
s.top()	q.front()
s.empty()	q.empty()

栈的基本应用包括括号匹配、后缀表达式的计算；队列的基本应用有约瑟夫问题等。
栈在解决中缀到后缀的转换问题时需要准备一个符号栈，对于中缀表达式，当读到一个操作数时立即输出；当读到操作符时根据运算符优先级选择入栈或输出。

树、二叉树、平衡树

树的一般标程

链表型结构的大多数操作花费线性时间，而树的大部分操作的运行时间平均为 O(logN)。树的遍历有三种方式，以根节点位置作划分，有先序遍历、中序遍历、后序遍历，亦有基于广度优先搜索（BFS）的层序遍历（level-order traversal）。

struct BTree{
    int val;
    BTree* left;
    BTree* right;
    BTree(int x) : val(x), left(nullptr), right(nullptr) {}
};

void preorder(BTree* root){
    if(root == nullptr)
        return;
    visit(root);
    preorder(root->left);
    preorder(root->right);
}

// 求二叉树的最大深度
int maxDepth(BTree* root){
    if(root == nullptr)
        return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

// 层次遍历
vector<vector<int>> levelTraverse(Btree* root){
    queue<Btree*> q;
    vector<vector<int>> res;
    if(root == nullptr) return;
    q.push(root);
    while(!q.empty()){
        int len = q.size();
        vector<int> tmp;
        for(int i = 0; i < len; i++){
            BTree* p = q.front();
            tmp.push_back(p->val);
            q.pop();
            if(p->left) q.push(p->left);
            if(p->right) q.push(p->right);
        }
        res.push_back(tmp);
    }
    return res;
}

// 最近公共祖先 LCA
BTree* lca(BTree* root, BTree* p, BTree* q){
    if(root == nullptr) return nullptr;
    if(root == p || root == q) return root;
    BTree* L = lca(root->left, p, q);
    BTree* R = lca(root->right, p, q);
    if(L != nullptr && R != nullptr) return root;
    if(L != nullptr && R == nullptr) return L;
    if(L == nullptr && R != nullptr) return R;
    return nullptr;
}

// 树上节点间距离
int distance(BTree* root, BTree* p, int dis){
    if(root == nullptr) return 0;
    if(root->left == p || root->right == p) return dis;
    return max(distance(root->left, p, dis + 1), distance(root->right, p, dis + 1));
}

// dis = distance(_lca, p, 0) + distance(_lca, q, 0)

二叉搜索树

二叉搜索树（Binary search tree）的性质是左子树节点值小于根节点小于右节点，查找的平均复杂度为 O(logN)。BST 的删除操作较为复杂，非必要情况可考虑懒惰删除（lazy deletion）。对 BST 进行中序遍历即可得到排好序的数据，平均复杂度为 O(logN)。

// TODO: 有重计数、前驱后继查找、懒惰删除
int bnt;
struct node{
    int val, ch[2];
}BST[100005];

void insert(int pos, int x){
    int u = BST[pos].ch[1];
    int tmp = u;
    while(u){
        tmp = u;
        u = BST[u].ch[x > BST[u].val];
    }
    bnt++;
    BST[tmp].ch[x > BST[tmp].val] = bnt;
    BST[bnt].val = x;
}

int queryVal(int pos, int x){
    int u = BST[pos].ch[1];
    while(u && BST[u].val != x)
        u = BST[u].ch[x > BST[u].val];
    if(BST[u].val == x)
        return u;
    else return 0;
}

// BST 的中序遍历即排序结果
void inOrder(int root){
    if(root == 0) return;
    inOrder(BST[root].ch[0]);
    printf("%d ", BST[root].val);
    inOrder(BST[root].ch[1]);
    return;
}

平衡树与 splay

插入和删除操作会破坏 BST 的结构，导致查找等操作更倾向于最坏情况，因此我们又提出了附带平衡条件的 AVL 平衡树，在删除时通过左旋/右旋（rotation）的方式调整，使左右子树的高度趋于平衡。

几乎所有的平衡树的平均性能均在 O(logN)，只在常数上有些许差异，ACM 一般也不会去卡平衡树的常数。因此我们至少需要熟练掌握一种平衡树的写法即可解决绝大多数的问题。

伸展树（splay）是一种相对简单的平衡树，每次操作的摊还代价为 O(logN)。它的特点是将被访问的节点通过旋转的方式变成根节点，切合 LRU 策略。伸展的情形有如下两种情况，一子形（zig-zig）和之字形（zig-zag）。

int root, snt; // 根位置，节点总数
struct node{
    int father; // 父节点
    int val; // 权值
    int siz; // 子树节点个数，包含等值节点和子树根
    int cnt; // 等值节点个数
    int ch[2]; // 左右子节点
}sp[100005];

void update(int pos){
    sp[pos].siz =  sp[sp[pos].ch[0]].siz + sp[sp[pos].ch[1]].siz + sp[pos].cnt;
}

int identify(int pos){
    return sp[sp[pos].father].ch[0] == pos? 0 : 1;
}

void connect(int pos, int fa, int son){
    sp[pos].father = fa;
    sp[fa].ch[son] = pos;
}

void rotate(int pos){
    int y = sp[pos].father;
    int R = sp[y].father;
    int Rson = identify(y);
    int yson = identify(pos);
    int B = sp[pos].ch[yson ^ 1];
    connect(B, y, yson); connect(y, pos, yson ^ 1);
    connect(pos, R, Rson);
    update(y); update(pos);
}

void splay(int pos, int goal){
    while(sp[pos].father != goal){
        int up = sp[pos].father;
        if(sp[up].father == goal)
            rotate(pos);
        else if(identify(pos) == identify(up)){
            // 一子形上旋
            rotate(up); rotate(pos);
        }
        else{
            // 之字形上旋
            rotate(pos); rotate(pos);
        }
    }
    if(goal == 0)
        root = pos; // 上旋至根节点
}

void insert(int x){
    int u = root, fa = 0;
    while(u && sp[u].val != x){
        fa = u;
        u = sp[u].ch[x > sp[u].val]; // 大于则右插
    }
    if(u)
        sp[u].cnt++; // 有等值节点
    else{
        u = ++snt;
        if(fa) sp[fa].ch[x > sp[fa].val] = u;
        sp[snt].ch[0] = sp[snt].ch[1] = 0;
        sp[snt].father = fa; sp[snt].val = x;
        sp[snt].siz = sp[snt].cnt = 1;
    }
    splay(u, 0);
}

// 查询树中已存在值 x
void queryVal(int x){
    int u = root;
    if(!u) return;
    while(sp[u].ch[x > sp[u].val] && x != sp[u].val)
        u = sp[u].ch[x > sp[u].val];
    splay(u, 0);
}

// 查询某值的前驱或后继
int queryNext(int x, int f){
    queryVal(x);
    int u = root;
    if((sp[u].val > x && f) || (sp[u].val < x && !f))
        return u;
    u = sp[u].ch[f];
    while(sp[u].ch[f ^ 1])
        u = sp[u].ch[f ^ 1];
    return u;
}

void del(int x){
    int pre = queryNext(x, 0);
    int post = queryNext(x, 1);
    splay(pre, 0); splay(post, pre);
    int d = sp[post].ch[0];
    if(sp[d].cnt > 1){
        sp[d].cnt--;
        splay(d, 0);
    }
    else sp[post].ch[0] = 0;
}

int queryKth(int k){
    int u = root;
    if(sp[u].siz < k) return -1;
    while(true){
        int y = sp[u].ch[0];
        if(k > sp[y].siz + sp[u].cnt){
            k -= sp[y].siz + sp[u].cnt;
            u = sp[u].ch[1];
        }
        else if(k <= sp[y].siz)
            u = y;
        else return sp[u].val;
    }
}

STL 中 set（数据不可重）和 multiset（数据可重）的底层实现为红黑树，在数据友好不卡常的 ACM 题中可用来代替手写平衡树逃课。

multiset<int> s;
multiset<int>::iterator it;

int queryVal(int x){
    it = s.lower_bound(x);
    multiset<int>::iterator i = s.begin();
    int pos = 0;
    while(i != it){
        pos++;
        i++;
    }
    return pos;
}

int queryKth(int k){
    int pos = 0;
    it = s.begin();
    while(pos != k){
        pos++;
        it++;
    }
    return *it;
}

int queryNext(int x, int f){
    if(f == 0){
        it = s.lower_bound(x);
        it--;
        return *it;
    }
    else{
        it = s.upper_bound(x);
        return *it;
    }
}

B-树是一种多路平衡搜索树，常用于数据库系统，它的特点是所有的数据都存储在树叶上，位于相同的深度，在进行插入操作时可能会发生分裂或长高。

散列

散列是一种用于以常数平均时间执行插入、删除和查找的技术，通过散列函数形成键值对映射。例如一串只包含小写英文字母的字符串即可映射为唯一的 26 进制数。常用的手写哈希为 $\text{hash}(x)=R-(x\bmod R)$，其中 $R$ 是小于表大小的任一素数（19260817、233）。

unordered_map<int, int> mat; // O(1)

散列并不能完全保证映射结果一定唯一，因此我们需要解决发生冲突的手段：

分离链接法：利用链表存储冲突元素
开放定址法：冲突即尝试选择其他单元
- 线性探测法
- 平方探测法
双散列：$F(x)=i\cdot\text{hash}(x)$
再散列：倍增表大小形成新的散列表（散列函数也要替换）
可扩散列：B-树

如果使用平方探测，且表的大小是素数，那么当表至少有一半是空的时候，总能够插入一个新的元素。

TODO: 字符串哈希

优先队列（堆）

相较于队列，优先队列的标程有方法 Insert（等价于入队）、DeleteMin，它的工作是找出、返回和删除优先队列中最小的元素。优先队列的通常实现方式是二叉堆。

priority_queue<int> pq; // 默认是大顶堆
priority_queue <int, vector<int>, greater<int>> pq; // 小顶堆

struct node{
    int t;
    inline bool operator<(const node &a) const{
        return t < a.t;
    }
}a[105];
priority_queue <node> q; // 默认大顶堆，可以修改结构体内部的排序规则转换为小顶堆

堆是一棵完全二叉树，因此我们可以方便的用数组来表示堆。对于数组中任一位置 $i$ 上的元素，其左儿子位于 $2i$，右儿子位于 $2i+2$，父亲位于 $\lfloor i/2\rfloor$。

堆序性质：最小/大元位于根，FindMin 操作为 O(1)
上滤（percolate up）：插入元素时与父结点进行比较，上滤至正确位置
下滤（percolate down）：删除最小元后子结点需上移至正确位置
实践中经常将堆的原始根节点作为标记（sentinel），设为 INF

堆在执行合并等操作时是比较复杂的，左式堆、斜堆、二项队列等均支持以 O(logN) 实现合并，它们之间的关系可类比为平衡树、伸展树和森林，这里暂且不表。

排序

基于比较的排序算法复杂度下界为 O(NlogN)；基于交换的非分治排序算法（如插入、冒泡），排序时交换元素的总次数为原始数组的逆序数；N 个互异数的数组的平均逆序数是 N(N-1)/4，因此通过交换相邻元素的排序算法复杂度下界为 O(N^2)。

插入排序：扫描有序数组插入新元素，O(N^2)
冒泡排序：双循环比较相邻元素，O(N^2)
希尔排序：根据增量序列递减比较元素，O(N^3/2)
堆排序：小/大顶堆，O(NlogN)
归并排序：递归合并两个有序数组，O(NlogN)，由于需要额外的线性附加内存，一般不用于主存排序而多用于外部排序
快速排序：选基准（pivot），递归排序，O(NlogN)
桶排序：用额外的一个桶（数组）记录频次，O(N)

int a[100005];
sort(a, a + n), stable_sort(a, a + n); // 内置快排

void qsort(int L, int R){
    
}

// 快速选择，第 k 大/小问题

基于比较的排序可以用决策树来表示每次比较的可能结果，对 N 个元素排序的决策树必然有 N! 个树叶，因此最坏情况至少需要 log(N!) 次比较。

不相交集（并查集）

并查集为解决集合内元素分类问题提供了一种灵巧的思路，初始认为所有元素独立，若元素同类则相关联；使用路径压缩技巧可优化 Union/Find 例程。

int find(int pos){
    int root = pos, tmp;
    while(root != a[root])
        root = a[root];
    // 路径压缩
    while(pos != a[pos]){
        tmp = a[pos];
        a[pos] = root;
        pos = tmp;
    }
    return root;
}

图论算法

图的表示、存储及遍历

一个图 $G=(V,E)$ 由顶点（vertex）集和边（edge）集组成。图分为有向（directed）图和无向图；有向无圈图可简称为 DAG；有向图连通则称为是强连通（strongly connected）的，有向图不连通但它的基础图（无向）连通则称为是弱连通（weakly connected）的。完全图（complete graph）是其每一对顶点间都存在一条边的图。
针对有向连通图有两种通用的遍历方式，即深度优先搜索（DFS）和广度优先搜索（BFS）。

int edge[MAX][MAX]; // 邻接矩阵
vector<int> edge[100005]; // 邻接表
bool vis[100005]; // 记忆
queue<int> q;

// int n = #node;
void dfs(int pos, int cur){
    if(cur > n) return;
    vis[pos] = true;
    printf("%d ", pos);
    for(int i = 0; i < edge[pos].size(); i++){
        if(!vis[edge[pos][i]])
            dfs(edge[pos][i], cur + 1);
    }
}

void bfs(int pos){
    vis[pos] = true;
    q.push(pos);
    while(!q.empty()){
        int u = q.front();
        printf("%d ", u);
        q.pop();
        for(int i = 0; i < edge[u].size(); i++){
            if(!vis[edge[u][i]]){
                q.push(edge[u][i]);
                vis[edge[u][i]] = true;
            }
        }
    }
}

除了使用邻接表和邻接矩阵存储图外，在竞赛中经常使用的一种数据结构叫做链式前向星，相较于使用 STL 的 vector 邻接表要快上很多。

int cnt = 1, head[100005]; // 记录以 i 节点为起点的最后一条边
struct node{
    int to; // 边的终点
    int dis; // 边的权值
    int next; // 同起点的上一条边
}edge[100005];

void add_edge(int u, int v, int w){
    edge[cnt].to = v;
    edge[cnt].dis = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
// cnt = #edge + 1
for(int i = 1; i < cnt; i++){
    // 遍历以 i 为起点的出边
    for(int e = head[i]; e; e = edge[e].next)
        printf("%d ", edge[e].dis);
}

拓扑排序

拓扑排序是对有向无圈图的顶点的一种排序，可以看做按照图的顶点连接顺序对顶点遍历的过程，常见的应用场景有课程的先后修、活动的先决条件等。算法的主要流程如下：

按给定数据流建立图，记录每个顶点的入度
将入度为 0 的节点放入队列
取出队首，遍历其出边，将能够到达的节点入度减一；将入度变成 0 的顶点加入队列
重复上两步，直到队列为空

int n, m, cnt = 1, head[15], ind[15];
struct node{
    int to, next;
}edge[15];
queue<int> q;

// m = #node
void topsort(int m){
    for(int i = 1; i <= m; i++){
        if(ind[i] == 0)
            q.push(i);
    }
    while(!q.empty()){
        int u = q.front();
        printf("%d ", u);
        q.pop();
        for(int e = head[u]; e; e = edge[e].next){
            int v = edge[e].to;
            ind[v]--;
            if(ind[v] == 0)
                q.push(v);
        }
    }
}

最短路径

单源最短路径问题的描述是：给定一个非负赋权图 $G=(V,E)$ 和一个特定节点 $v$ 作为输入，找出 $v$ 到图中每一个其他节点的最短赋权路径。解决这个问题的通用方法是 Dijkstra 算法，时间复杂度上限为 O(n^2)，堆优化后可降至 O((N + M)logN)。它的算法流程如下：

节点分为两类，已确定最短路径的点和未确定的点
初始化 dis[start] = 0，其余节点的 dis 为无穷大
找出 dis 值最小的节点设为已确定最短路径
遍历该节点所有的出边 $(x,y,t)$，dis[y] = min(dis[y], dis[x] + z)
重复上述步骤直至所有节点均已确定

int n, m, cnt = 1, head[15], dis[15];
bool vis[15];
struct nod{
    int to, dis, next;
}edge[15];

void add_edge(int u, int v, int w){
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    edge[cnt].dis = w;
    head[u] = cnt++;
}
// 图中节点
struct node{
    int dis, pos;
    inline bool operator<(const node &t) const{
        // 注意优先对列默认为大根堆，这里要调整方向
        return dis > t.dis;
    }
};
priority_queue<node> q; // 小根堆

// s 是源节点
void dijkstra(int s){
    dis[s] = 0;
    q.push((node){0, s});
    while(!q.empty()){
        node tmp = q.top();
        q.pop();
        int u = tmp.pos;
        if(vis[u]) continue;
        vis[u] = 1;
        for(int e = head[u]; e; e = edge[e].next){
            int v = edge[e].to;
            if(dis[v] > dis[u] + edge[e].dis){
                dis[v] = dis[u] + edge[e].dis;
                if(!vis[v])
                    q.push((node){dis[v], v});
            }
        }
    }
}

Dijkstra 算法的本质思想是贪心（具有最优子结构），它只适用于不含负权边的图。如果图具有负边值，spfa 算法会是一个很好的选择，spfa 亦可用于判断图中是否存在负环。spfa 的实质是通过 BFS 使得所有的边对组合均满足三角不等式，因此算法的复杂度上界是 O(EV)，所以不建议在非负权图中使用 spfa。

// TODO: 看懂它
void spfa(int s){
    for(int i = 1; i <= n; i++){
        dis[i] = 0x7fffffff;
        vis[i] = true;
    }
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    vis[s] = false;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = true;
        for(int i = head[u]; i; i = edge[i].next){
            int v = edge[i].to;
            if(dis[v] > dis[u] + edge[i].dis){
                dis[v] = dis[u] + edge[i].dis;
                if(vis[v]){
                    q.push(v);
                    vis[v] = false;
                }
            }
        }
    }
}

对于无圈图，可结合拓扑排序来改进 dijkstra，在拓扑排序的同时选择和更新，算法可以一趟完成，运行时间为 O(E + V)。它的一个常见应用场景为对关键路径的分析。

多源最短路径问题的描述是：给定一个非负赋权图，求图中任意两节点间的最短赋权路径，解决这个问题的通用方法是 Floyd 算法，复杂度为 O(n^3)，算法的核心思想是遍历两节点间的所有中间节点判断是否经过即可。

for(int k = 1; k <= n; k++){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(edge[i][j] > edge[i][k] + edge[k][j])
                edge[i][j] = edge[i][k] + edge[k][j];
        }
    }
}

网络流问题

（洛谷蓝题，暂且不表，课本给出的应该是 EK 算法）

最小生成树

一个连通图的生成树是指一个连通子图，它含有图中全部 n 个顶点和 n - 1 条边，如果往生成树中再添加一条边则必定成环。在连通图的所有生成树中，所有边的代价和最小的生成树称为最小生成树。最小生成树的构造有两种算法，分别是 Prim 算法和 Kruskal 算法。

Kruskal 算法的思想是贪心加边，把图中的 n 个顶点看成独立的 n 棵树组成的森林，选择满足条件的最小代价边并合并（并查集）

int n, m, eu, ev, res, a[200005];
struct node{
    int u, v, w;
    inline bool operator<(const node& t) const{
        return w < t.w;
    }
}edge[200005];

void kruskal(){
    sort(edge, edge + m);
    for(int i = 0; i < m; i++){
        eu = find(edge[i].u);
        ev = find(edge[i].v);
        if(eu == ev) continue;
        else{
            res += edge[i].w; // 最小生成树的路径和
            a[ev] = eu; cnt++; // 合并
            if(cnt == n - 1)
                break;
        }
    }
}

图的连通性问题

由于该章节洛谷均为蓝绿题，暂且不表，日后更新