算法-数据结构

发表于 2022-07-20 更新于 2023-01-21

包括了常用的，从基础到复杂的数据结构

栈

栈是一种后进先出的数据结构。

栈的一大用处是做算数表达式的计算。算数表达式通常有前缀、中缀、后缀三种。

中缀表达式，最常见的表达式
前缀表达式，形如"op A B"，其中 A B 是另外两个前缀表达式，op 是运算符，如* 3 - 1 2
后缀表达式，形如"A B op"，其中 A B 是另外两个后缀表达式，op 是运算符，如1 2 - 3 *

后两种表达式不需要使用括号，其运算方案唯一确定。

前后缀表达式求值

后缀表达式求值：

建立一个用于存数的栈，逐一扫描该后缀表达式中的元素
1. 如果遇到一个数，则把该数入栈
2. 如果遇到运算符，就取出栈顶的两个数进行计算，把结果入栈
扫描完成后，栈中恰好剩下一个数，就是该后缀表达式的值

中缀表达式转后缀表达式：

建立一个用于存运算符的栈，逐一扫描该中缀表达式中的元素
1. 如果遇到一个数，输出该数
2. 如果遇到左括号，把左括号入栈
3. 如果遇到右括号，不断取出栈顶并输出，直到栈顶为左括号，然后把左括号出栈
4. 如果遇到运算符，只要栈顶符号的优先级不低于新符号，就不断取出栈顶并输出，最后把新符号进栈。优先级为乘除>加减>左括号
依次取出并输出栈中的所有剩余符号，最终输出的序列就是一个与原中缀表达式等价的后缀表达式

队列

队列是一种“先进先出”的线性数据结构。

链表与邻接表

略

Hash表

Hash表又称散列表，一般由Hash函数和链表结构共同实现。我们可以用Hash函数将复杂的信息映射到一个容易维护的值域内。有可能造成冲突。使用开散列解决。建立一个邻接表结构，以Hash函数的值域作为表头数组，映射后的值相同的原始信息被分到一类。

Hash表主要包括两种操作：

计算Hash函数的值
定位到对应链表中依次遍历、比较

字符串Hash

取一固定值，把字符串看作P进制数，并分配一个大于0的数值，代表每种字符。可以令a=1,b=2…z=26。取一固定值M，求出该P进制数对M的余数，作为该字符串的Hash值。

一般取P=131或P=13331，此时冲突概率最低。一般取M=2⁶⁴，即使用unsigned long long存储该值，利用自然溢出取模。

对字符串的各种操作，都可以直接对P进制数进行算术运算后反映到Hash值上。

如果我们已知字符串S的Hash值为H(S)，那么在S后添加一个字符c构成新字符串的Hash值就是H(S+c)=(H(S)*P+value[c]) mod M。

如果我们已知字符串S的Hash值为H(S)，字符串S+T的Hash值为H(S+T)，则字符串T的Hash值为 H(T)=(H(S+T)-H(S)*P^length(T)) mod M。

根据上面两种操作，我们可以在 O(n) 时间预处理字符串所有前缀Hash值。

// 预处理 f 与 p
for (int i = 1; i <= n; i++)
{
    p[i] = p[i - 1] * 131;
    f[i] = f[i - 1] * 131 + (s[i] - 'a' + 1);
}

// s[i~j]对应的Hash值
f[j] - f[i-1] * p[j-i+1]

字符串

KMP

KMP算法能够在线性时间内判断字符串A是否为B的字串，并求出A在B中各次出现的位置。
KMP算法分为两步：

对字符串A进行自我匹配，求出一个数组 next ，其中 next[i] 表示“ A 中以 i 结尾的非前缀字符串”与“A 的前缀”能够匹配的最长长度，即：

next[i]=max\{j\}, j < i \ \& \ A[i-j+1 \sim i]=A[1 \sim j]

特别的，当不存在这样的 j 时，令 next[i] = 0。
2. 对字符串A与B进行匹配，求出一个数组f，其中 f[i] 表示“B 中以 i 结尾的字串”与“A的前缀”能够匹配的最长长度，即：

f[i]=max\{j\}, j < i \ \& \ B[i-j+1 \sim i]=A[1 \sim j]

朴素的做法是枚举 j ∈ [1,i-1] 计算 next 数组。dp优化的算法可以在 O(n) 的复杂度计算 next 数组。

引理
若 j₀ 是 next[i] 的一个“候选项”，即 j₀ < i 且 A[i-j₀+1~i]=A[1~j₀]，则小于 j₀ 的最大的 next[i] 的候选项是 next[j₀]。

根据引理，当 next[i-1] 计算完毕时，我们即可得知 next[i-1] 的所有“候选项” 从大到小依次是 next[i-1]，next[next[i-1]]…而如果一个整数 j 是 next[i] 的候选项，那么 j-1 显然也是 next[i-1] 的候选项，因此在计算 next[i] 时，只要把 next[i-1]+1，next[next[i-1]]+1…作为 j 的选项即可。

KMP算法next数组的求法

初始化next[1]=j=0，假设next[1 ~ i-1]已求出，下面求解 next[i]。
不断尝试扩展匹配长度 j，如果扩展失败（下一个字符不相等），令 j
变为 next[j]，直至 j 为0（应该从头开始匹配）。
如果能够扩展成功，匹配长度 j 就增加 1。 next[i] 的值就是 j。

ne[1] = 0;
for (int i = 2, j = 0; i <= n; i++)
{
    while (j > 0 && a[i] != a[j+1])
        j = ne[j];
    if (a[i] == a[j+1])
        j++;
    ne[i] = j;
}

因为定义的相似性，求解 f 与求解 next 的过程基本一致

for (int i = 1, j = 0; i <= m; i++)
{
    while (j > 0 && (j == n || b[i] != a[j+1]))
        j = ne[j];
    if (b[i] == a[j+1])
        j++;
    f[i] = j;
    // if f[i] == n，此时找到了一解
}

Trie

Trie（字典树）是一种用于实现字符串快速检索的多叉树结构。

初始化
一棵空Trie仅包含一个根节点，该点的字符指针均指向空。

插入
当需要插入一个字符串S时，我们令一个指针P起初指向根节点。然后，依次扫描S中的每一个字符C。

若P的c字符指针指向一个已经存在的节点Q，则令P=Q。
若P的c字符指针指向空，则新建一个节点Q，令P的c字符指针指向Q，然后令P=Q。

当S中的字符扫描完毕时，在当前节点P上标记它是一个字符串的末尾。

检索
当需要检索一个字符串S在Trie中是否存在时，我们令一个指针P起初指向根节点，然后依次扫描S中的每个字符c：

若P的c字符指针指向空，则说明S没有插入过Trie，结束检索
若P的c字符指针指向一个已经存在的节点，则令P=Q。

当S中的字符扫描完毕时，若当前节点P被标记为一个字符串的末尾，则说明S在Trie中存在，否则说明S没有插入过Trie。

int trie[N][26], tot = 1;
void insert(char *str)
{
    int len = strlen(str), p = 1;
    for (int k = 0; k < len; k++)
    {
        int ch = str[k]-'a';
        if (trie[p][ch] == 0)
            trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
    end[p] = true;
}

bool search(char *str)
{
    int len = strlen(str), p = 1;
    for (int k = 0; k < len; k++)
    {
        int ch = str[k] - 'a';
        if (trie[p][ch] == 0)
            return false;
        p = trie[p][ch];
    }
    return end[p];
}

二叉堆

二叉堆是一种支持插入、删除、查询最值的数据结构。

若树中的任意节点的权值都小于等于其父节点的权值，则称该二叉树满足“大根堆”性质。反之满足小根堆性质。

根据完全二叉树的性质，可以使用层次序列存储方法，使用数组保存二叉堆。父节点编号等于子节点编号除以2，左子节点编号等于父节点编号乘2，右子节点编号等于左子节点编号乘2加1。

Insert
在大根堆中插入新节点，首先把新节点放在数组末尾，然后通过交换的方式向上调整，时间复杂度为O(logn)。

void up(int p)
{
    while (p > 1)
    {
        if (heap[p] > heap[p/2])
        {
            swap(heap[p], heap[p/2]);
            p /= 2;
        }
        else
            break;
    }
}

void insert(int val)
{
    heap[++n] = val;
    up(n);
}

GetTop
返回堆顶值，即全局最大值

1	int getTop() { return heap[1]; }

Extract
移除堆顶。先将堆顶与数组末尾heap[n]交换，然后移出末尾，最后将堆顶向下交换。

void down(int p)
{
    int s = p * 2; // 左子节点
    while (s <= n)
    {
        if (s < n && heap[s] < heap[s+1])
            s++;
        if (heap[s] > heap[p])
        {
            swap(heap[s], heap[p]);
            p = s, s = p * 2;
        }
        else
            break;
    }
}

void extract()
{
    heap[1] = heap[n--];
    down(1);
}

Remove
把下标p位置的节点删除。类似于extract，对于节点p，分别向上和向下调整。

void remove(int k)
{
    heap[k] = heap[n--];
    up(k), down(k);
}

Huffman树

考虑构造一棵包含 n 个叶子节点的k叉树，其中第 i 个叶子节点带有权值 w_i，要求最小化 ∑w_i * l_i，其中 l_i 表示第 i 个叶子节点到根节点的距离。解为Huffman树。

考虑二叉树，有如下方法构造Huffman树：

建立一个小根堆，插入这 n 个叶子节点的权值
从堆中取出最小的两个权值 w₁ 和 w₂，令 ans += w₁ + w₂。
建立一个权值为 w₁ + w₂ 的树节点 p，令 p 成为权值为 w₁ 和 w₂ 的树节点的父亲。
在堆中插入权值 w₁ + w₂。
重复 2~4 步，直至堆的大小为 1。

此时，ans 就是 ∑ w_i * l_i 的最小值。

对于 k 叉 Huffman树，改为每次从堆中取出最小的 k 个权值。显然，当堆中不足 k 个数时，将之前叶节点移到新的层次上将减小 sum。故，执行该算法前，需要补充一些权值为 0 的叶节点，使得 (n-1) mod (k-1) = 0，这样才能使得贪心正确。

并查集

并查集可以动态维护若干个不重叠的集合，支持合并与查询，包括如下两个基本操作：

查询元素属于哪个集合
把两个集合合并成一个大集合

并查集使用代表元法，为每个集合选取一个固定元素作为代表。集合是树形结构，树根是代表元素。为提高效率，通过路径压缩，在查找时将树根作为所有子节点的直接父节点。

int p[N]; // 子节点的父节点

// 初始化
for (int i = 1; i <= n; i++)
    p[i] = i;

int find(int x)
{
    if (p[x] == x)
        return x; // 父节点是自身，说明 x 为代表元
    return p[x] = find(p[x]);
}

// 合并
p[find(a)] = find(b); // 将 a 合并到 b

“扩展域”与“边带权”的并查集

我们可以维护一个数组d，用 d[x] 保存节点 x 到父节点 p[x] 之间的边权。在每次路径压缩后，每个访问过的节点都会直接指向树根，如果我们同时更新这些节点的 d 值，就可以利用路径压缩过程来统计每个节点到树根之间的路径上的一些信息。

void merge(int a, int b)
{
    p[a] = b;
    d[a] = l[b];
    l[b] += l[a];
}

int find(int x)
{
    if (x == p[x])
        return x;
    int r = find(p[x]);
    d[x] += d[p[x]];
    return p[x] = r;
}

树状数组

若一个正整数 $x$ 的二进制表示为 $a_{k-1}a_{k-2}···a_2a_1a_0$ ，其中等于 1 的位是 $\{a_{i_1},a_{i_2},···a_{i_m}\}$ ，则正整数 $x$ 可以被二进制分解成：

x=2^{i_1}+2^{i_2}+···+2^{i_m}

不妨设 $i_1>i_2>···i_m$ ，进一步地，区间 $[1,x]$ 可以被分解成 $O(logn)$ 个小区间：

长度为 $2^{i_1}$ 的区间 $[1,2^{i_1}]$
长度为 $2^{i_2}$ 的区间 $[2^{i_1}+1,2^{i_1}+2^{i_2}]$
长度为 $2^{i_3}$ 的区间 $[2^{i_1}+2^{i_2}+1,2^{i_1}+2^{i_2}+2^{i_3}]$
···

这些区间的共同特点是：若区间结尾为 $r$ ，则区间长度就等于 $lowbit(r)$ 。

树状数组基于上述思想，维护序列的前缀和。对于给定的序列 $a$ ，建立一个数组 $c$ ，其中 $c[x]$ 保存序列 $a$ 的区间 $[x-lowbit(x)+1,x]$ 中所有数的和，即 $\sum^{x}_{x-lowbit(x)+1}a[i]$ 。

该结构满足以下性质：

每个内部节点 c[x] 保存以它为根的子树中所有叶节点的和。
每个内部节点 c[x] 的子节点个数等于 lowbit(x) 的位数
除树根外，每个内部节点 c[x] 的父节点是 c[x+lowbit(x)]
树的深度为 O(logN)

如果 N 不是 2 的整次幂，那么树状数组就是一个具有同样性质的森林结构。

树状数组支持的基本操作有两个，第一个操作是查询前缀和，即序列 a 第 1~x 个数的和。按照原理将 x 拆分成若干个小区间即可。

int ask(int x)
{
    int ans = 0;
    for (; x; x -= x & -x)
        ans += c[x];
    return ans;
}

第二个操作是单点增加。任意一个节点的祖先节点最多有 logN 个，逐个增加即可。

int add(int x, int v)
{
    for(; x <= N; x += x & -x)
        c[x] += v;
}

较为简便的一种初始化方法是，建立全为0的数组并对每个位置add(x,a[x])。

树状数组与逆序对

给定一个集合 a，如果用 t[val] 保存数值 val 在集合中出现的次数，那么 t 在 [l, r] 上的区间和就代表集合 a 中范围在 [l,r] 内的数有多少个。

我们可以在集合 a 的数值范围上建立树状数组，维护 t 的前缀和。

利用树状数组求一个序列的逆序对个数：

在序列 a 的数值范围上建立树状数组，初始化全为 0。
倒序扫描给定的序列 a，对于每个数 a[i]:
1. 在树状数组中查询前缀和 [1,a[i]-1]，累加到答案中
2. 执行单点增加，把 a[i] 上的数累加 1。
ans 即为所求。

for (int i = n; i; i--)
{
    ans += ask(a[i] - 1);
    add(a[i], 1);
}

线段树

线段树是一种基于分治思想的二叉树结构，用于在区间上进行信息统计。

线段树的每个节点都代表一个区间
线段树具有唯一的根节点，代表的区间是整个统计范围
线段树的每个叶节点都代表一个长度为 1 的元区间
对于每个内部节点 [l,r]，它的左子节点是 [l,mid]，右子节点是 [mid+1,r]，其中 mid=(l+r)/2 （向下取整）。

除去线段树的最后一层，其是一个完全二叉树。依旧用类似于二叉堆的节点编号方式。

根节点编号为 1
编号为 x 的节点的左子节点编号为 x*2，右子节点编号为 x*2+1

使用struct数组来保存线段树。显然，数组长度要不小于 4N 才能保证不会越界。

// 以求最大值为例
struct SegmentTree {
    int l, r;
    int dat;
} t[N * 4];

建树

void build(int p, int l, int r)
{
    t[p].l = l. t[p].r = r;
    if (l == r)
    {
        t[p].dat = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(p*2, l, mid);
    build(p*2+1, mid+1, r);
    t[p].dat = max(t[p*2].dat, t[p*2+1].dat);
}

build(1, 1, n);

单点修改
线段树的单点修改是一条形如"C x v"的指令，表示把 A[x] 的值修改为 v。

在线段树中，根节点是执行各种指令的入口。我们需要从根节点出发，递归找到代表 [x,y] 的叶节点，然后从下往上更新它所有的祖先节点。

void change(int p, int x, int v)
{
    if (t[p].l == t[p].r)
    {
        t[p].dat = v;
        return;
    }
    int mid = (t[p].l + t[p].r) / 2;
    if (x <= mid)
        change(p*2, x, v);
    else
        change(p*2+1, x, v);
    t[p].dat = max(t[p*2].dat, t[p*2+1].dat);
}

change(1, x, v);

区间查询
区间查询是一条形如“Q l r”的指令，查询 [l,r] 上的最大值。我们需要从根节点开始递归执行以下过程。

若[l,r]完全覆盖了当前节点代表的空间，则立即回溯，并且该节点的dat值为候选答案
若左子节点与 [l,r] 有重叠部分，则递归访问左子节点
若右子节点与 [l,r] 有重叠部分，则递归访问右子节点

int query(int p, int l, int r)
{
    if (l <= t[p].l && r >= t[p].r)
        return t[p].dat;
    int mid = (t[p].l + t[p].r) / 2;
    int val;
    if (l <= mid)
        val = query(p*2, l, r);
    if (r > mid)
        val = max(val, query(p*2+1, l, r));
    return val;
}

延迟标记

在区间修改时，若修改 [l,r]，则以其为根子树上的所有节点都会被更新，时间复杂度为 $O(n)$ ，不能接受。

当我们修改区间时，可以和查询一样，在 $l \le p_l \le p_r \le r$ 的情况下直接返回，但是在回溯之前向节点 p 增加一个标记，标识“该节点曾经被修改，但其子节点尚未被更新”。

如果在后续的指令中，需要从节点 p 向下递归，再检查 p 是否有标记。若有标记，则根据标记信息更新 p 的两个子节点，同时为 p 的两个子节点增加标记，然后清除 p 的标记。

// 以区间和为例
void pushdown(int p)
{
    if (t[p].add)
    {
        t[p*2].sum += t[p].add * (t[p*2].r - t[p*2].l + 1);
        t[p*2+1].sum += t[p].add * (t[p*2+1].r - t[p*2+1].l + 1);
        t[p*2].add += t[p].add;
        t[p*2+1].add += t[p].add;
        t[p].add = 0;
    }
}

void change(int p, int l, int r, int v)
{
    if (l <= t[p].l && r >= t[p].r)
    {
        t[p].sum += (t[p].r - t[p].l + 1) * v;
        t[p].add += v;
        return;
    }
    pushdown(p);
    int mid = (t[p].l + t[p].r) / 2;
    if (l <= mid)
        change(p * 2, l, r, v);
    if (r > mid)
        change(p * 2 + 1, l, r, v);
    t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum;
}

ll query(int p, int l, int r)
{
    if (l <= t[p].l && r >= t[p].r)
        return t[p].sum;
    pushdown(p);
    int mid = (t[p].l + t[p].r) / 2;
    ll val = 0;
    if (l <= mid)
        val += query(p * 2, l, r);
    if (r > mid)
        val += query(p * 2 + 1, l, r);
    return val;
}

扫描线

// pass

分块

分块的基本思想是通过适当的划分，预处理一部分信息并保存下来，用空间换取时间。

对于数组操作，将数组分成若干个长度不超过 $\lfloor x \rfloor$ 的段，其中第 $i$ 段左端点为 $(i-1)\lfloor x \rfloor + 1$ ，右端点为 $min(i\lfloor x \rfloor, N)$ 。

预处理每段的所求值与增量标记，以区间和为例。

对于指令“C l r d”：

若 l 与 r 同时处于第 i 段内，则直接把 A[l]…A[r] 都加 d，同时令 sum[i] += d * (r-l+1)。
否则，设 l 处于第 p 段，r 处于第 q 段。
1. 对于 i ∈ [p+1,q+1]，令 add[i] += d。
2. 对于开头，结尾不足一整段的两部分，按照第一种情况朴素更新。

对于指令“Q l r”：

若 l 与 r 同时处于第 i 段内，则直接朴素计算。
否则，设 l 处于第 p 段，r处于第 q 段，初始化 ans = 0
1. 对于 i ∈ [p+1,q+1]，令 ans += sum[i] + add[i]*len[i]，其中len[i] 表示第 i 段的长度。
2. 对于开头结尾不足一整段的两部分，朴素计算。

分块后的时间复杂度为 $O(n\sqrt{n})$ 。

二叉查找树与平衡树

BST

给定一棵二叉树，树上的每个节点带有一个数值，称为节点的“关键码”。所谓“BST性质”是指，对于树中的任意节点：

该节点的关键码不小于它的左子树中任意节点的关键码
该节点的关键码不大于它的右子树中任意节点的关键码

满足上述性质的二叉树就是一棵二叉查找树，其中序遍历是一个单调递增的序列。

建立
额外插入正无穷、负无穷节点避免判断边界情况。

struct BST {
    int l, r; // 左右子节点的下标
    int val;  // 关键码
} a[N];

int New(int val)
{
    a[++tot].val = val;
    return tot;
}

void build()
{
    New(-0x3f3f3f3f), New(0x3f3f3f3f);
    root = 1, a[1].r = 2;
}

检索
设一棵子树根节点为 p

若 p 的关键码等于 val，则已找到
若 p 的关键码大于 val
1. 若 p 的左子节点为空，说明不存在val
2. 若 p 的左子节点不为空，在 p 的左子树中递归进行检索
若 p 的关键码小于 val
1. 若 p 的右子节点为空，说明不存在val
2. 若 p 的右子节点不为空，在 p 的右子树中递归进行检索

int get(int p, int val)
{
    if (p == 0) 
        return 0;
    if (val == a[p].val)
        return p;
    return val < a[p].val ? get(a[p].l, val) : get(a[p].r, val);
}

插入
若不存在关键码为 val 的节点。当搜索发现空时，直接赋值新节点即可。

void insert(int &p, int val)
{
    if (p == 0)
    {
        p = New(val);
        return;
    }
    if (val == a[p].val)
        return;
    if (val < a[p].val)
        insert(a[p].l, val);
    else
        insert(a[p].r, val);
}

求前驱/后继
以后继为例。后继是指关键码大于val的关键码最小的节点。
初始化 ans 为正无穷节点的编号。检索 val，每经过一个节点，都检查该节点能否更新所求的后继 ans。

没有找到 val 或找到的节点没有右子树
ans即为所求。
val的节点p有右子树
从 p 的右子节点出发，一直向左走。

int getNext(int val)
{
    int ans = 2;
    int p = root;
    while (p)
    {
        if (val == a[p].val)
        {
            if (a[p].r > 0) 
            {
                p = a[p].r;
                while (a[p].l > 0)
                    p = a[p].l;
                ans = p;
            }
            break;
        }
        if (a[p].val > val && a[p].val < a[ans].val)
            ans = p;
        p = val < a[p].val ? a[p].l : a[p].r;
    }
    return ans;
}