算法

基本算法

TODO旋转算法

旋转算法主要有这几种

• 手摇(三次)旋转

• 临时空间

• 循环置换(juggling/gcd)

• 块交换

我们来看Rust标准库的实现

type BufType = [usize; 32];
#[inline]
pub(super) const unsafe fn ptr_rotate<T>(left: usize, mid: *mut T, right: usize) {
	// 边界条件处理
    if T::IS_ZST {
        return;
    }
    if (left == 0) || (right == 0) {
        return;
    }
	
    if !cfg!(feature = "optimize_for_size")
        && core::cmp::min(left, right) <= size_of::<BufType>() / size_of::<T>()
    {
		// 当有left或right有一个块小到足以装进BufType规定的缓冲区时 使用memmove
        unsafe { ptr_rotate_memmove(left, mid, right) };
    } else if !cfg!(feature = "optimize_for_size")
		// 当左和右一共<24时 也就是旋转的总规模很小时 使用GCD算法
        && ((left + right < 24) || (size_of::<T>() > size_of::<[usize; 4]>()))
    {
	
        unsafe { ptr_rotate_gcd(left, mid, right) }
    } else {
        unsafe { ptr_rotate_swap(left, mid, right) }
    }
}

TODO贪心算法

每一步只做当前看起来最好的选择（局部最优），并期望这些局部最优能累积成全局最优。

贪心算法通常有两个特质:

1. 贪心选择性质: 全局最优可以通过局部最优选择来达到.

2. 最优子结构: 一个问题的最优解包含其字问题的最优解.

接下来我会给出各种贪心算法的证明

交换论证

我们需要证明 贪心解不差于最优解.

假设存在一个最优解 每一步的选择是

\[ (o_1,o_2,...,o_m) \]

而贪心解每一步的选择是

\[ (g_1,g_2,..,g_m) \]

那么我们选择其中一步 i

• 若 \(o_i = g_i\) 则两者一致 我们递归或者归纳的处理剩下的

• 若 \(o_i != g_i\) 那我们用\(g_i\) 替换 \(o_i\) 证明替换后的 \(o_1,o_2,...,g_i,...,o_m\) 不差于原来的

区间覆盖

1. 对于任意最短路径 如果第一步没有走到当前能到达的最远点 那么把第一步替换成最远点 不会增加后续步数

DP动态规划

动态规划的本质只有一件事

把重复计算的搜索 变成状态复用的递推

\[ dp[state] = min/max/\sum dp[sub_state] + cost \]

TODO搜索算法

BFS

广度优先搜索.

直观的来说 就是浅显的访问同一层的所有节点 然后再去下一层.

用二叉树来直观的看 就是: 先访问一层的所有兄弟节点 然后再往儿子节点去.

用矩阵来直观的看: 先访问上下左右的四个邻居 然后再访问这四个邻居的邻居...

在实现上 BFS使用一个队列来记录已经遍历了哪些.

那么BFS具有一个非常好的性质:

BFS 算法找到的路径是从起点开始的 最短 合法路

• 遍历二叉树

#[derive(Debug,PartialEq,Eq)]
pub struct TreeNode<T> {
	pub val: T,
	pub left: Option<Box<TreeNode<T>>>,
	pub right: Option<Box<TreeNode<T>>>,
}

use std::collections::VecDeque;

pub fn bfs(root: TreeNode<T>) -> Vec<T> {
    let mut queue = VecDeque::new();
    let mut result = Vec::new();
    queue.push_back(root);
    while let Some(node) = queue.pop_front() {
        result.push(node.val);
        if let Some(left) = node.left {
            queue.push_back(*left);
        }
        if let Some(right) = node.right {
            queue.push_back(*right);
        }
    }
    result
}

DFS

数据结构

区间数据结构

对区间进行操作的数据结构.

在实际的算法问题中, 我们经常需要: 如何高效的维护一个序列的区间信息.

为此 我们建立一个统一点的模型.

给定数组

\[ a_1,a_2,\cdots,a_n \]

主要的两种操作为: 查询与修改

• 查询: 查询 [l,r] 区间的信息, 比如它们的 和, 积, 最大值 ...

• 修改: 修改了 \(a_i\) 或者修改了 \(a_i,\cdots,a_j\)

于是产生了如下不同的数据结构:

数据结构	初始建表	查询	修改	表的空间复杂度
前缀和	O(n)	O(1)	O(n)	O(n)
差分数组	O(n)		O(1)	O(n)
ST表	O(nlogn)	O(1)		O(nlogn)
线段树	O(n)	O(logn)	单点/区间 O(logn)	O(n)
树状数组	O(n)	O(logn)	单点 O(logn)	O(n)

前缀和

不推荐修改 只查询. 维护[l,r]的 和

花费O(n)的时间建表 然后O(1)的时间 可以求出 \sum_{i=l}^r a_i.

令

\[ prefix[i] = \sum_{j=1}^{i} a_j \]

那么

\[ \sum_{i=l}^{r} a_i = prefix[r] - prefix[l-1] \]

比如 原数组 arr = [1,2,3,4,5,6]

前缀和数组为: prefix = [1,3,6,10,15,21]

那么查询 原数组的 [2,5] 的和 就是: prefix[5] - prefix[1]

差分数组

推荐修改. 维护 原数组的 一阶差分 但是保留第一个数.

花费O(n)的时间建表 花费O(1)的时间 可以对区间修改

与前缀和的不同是: 前缀和能方便的查询 而差分数组能方便的修改.

令 $\( diff[1] = a_1 \\ diff[i] = a_i - a_{i-1} , i > 1 \)$

那么 假如 对 区间[l,r] 所有元素 + n, 做下面两个操作即可.

• \(diff[l] += n\)

• \(diff[r+1] -= n\)

比如 原数组 arr = [1,2,5,9,23,25,50]

差分数组为: diff = [1,1,3,4,14,2,25]

那么给arr的[3,5]都加10就是: diff[3] + 10, diff[6] - 10

得到了 diff = [1,1,13,4,14,2,15]

恢复就是 arr = [1,2,15,19,33,35,50]

稀疏表(ST表)

ST表专门用来做 静态数组区间查询. 而且很适合处理 可重复贡献问题.

• 可重复贡献问题指的是 对于一个算子L, L(x,x) = x. 也就是说 max,gcd都是L算子

ST表存储: 从每个位置开始 长度为\(2^k\)的区间答案 , 也就是使用倍增思想.

花费O(nlogn)时间建表 表O(nlogn)大小 花费O(1)时间查询

ST表的存储为:

\[ st[k][i] \]

表示 从下标i开始 长度为\(2^k\)的区间的答案.

比如 原数组 arr = [2,3,5,1,4,6,7,0] 我们要存最大值.

• st[0][] = [2] [3] [5] [1] [4] [6] [7] [0]

• st[1][] = [3] [5] [5] [4] [6] [7] [7]

• st[2][] = [5] [5] [6] [7] [7]

• st[3][] = [7]

那么对于任意的[l,r], 我们O(1)时间可以得到答案

比如[3,6]. 我们先算距离大小: 6 - 3 + 1 = 4 那么直接是st[2][3].

比如[1,5]. 距离为: 5 - 1 + 1 = 5 我们直接取: [1,4] 与 [2,5] 取max.

也就是说: [1,4]与[2,5]可以求最大值为[1,5].

这也就是为什么要求ST表解决: 可重复问题 也就是f(x,x)=x, 否则重复将直接失效.

线段树

对一个数组 快速进行区间查询与修改.

• ST表 建表需要O(nlogn) 查询只要 O(1) 但修改不是很方便.

• 线段树 建表需要O(n) 查询需要O(logn) 但是单点修改与区间修改只需要O(logn)

线段树的修改是方便于ST表的.

具体而言 线段树是一颗二叉树. 它自顶向下的二分区间.

比如原数组 arr = [2,3,5,1,4,6,8,9]

• root: [2,3,5,1,4,6,8,9]

• root的左孩子与右孩子: [2,3,5,1],[4,6,8,9]

• ....

• [2] [3] [5] [1] [4] [6] [8] [9]

一共logn层

• 假设我们查询区间[2,6]的最大值, 那么[2,3],[4,5],[5,6]覆盖这个区间. 通常只需要查询O(logn)个区间 就可以覆盖这个区间. 所以查询是O(logn).

如果在root向下查询的时候 遇到了lazy标签 就把lazy标签累计上 最后子节点一起加起来

• 单点修改的话 每层改一个值即可 一共logn层

• 区间修改比较特殊 借助lazy propagation懒标记 将本来需要给整个子树做的操作 在它们的父节点就打个标记.

假设arr有16个元素. 我们需要修改[5,14] 都+10.

区间树会寻找完全覆盖[5,14]的几个节点: [5,8],[9,12],[13,14].

我们先把这几个节点都修改: sum[5,8] += 4*10 sum[9,12] += 4*10.

但是我们不去修改子节点: 比如[5,6] [7,8] [9,10] [11,12]

我们记录 lazy[5,8] = 10, lazy[9,12] = 10.

这样当我们查询[5,6]的时候: [1,16] -> [1,8] -> [5,8]. 看看有哪些lazy 然后加一起.

这样而来: 对于区间修改, 我们只需要修改O(logn)个节点 并给它们打lazy标记. 而查询的时候需要遍历最多logn层的祖先 来看看有没有lazy.

这样就保证了区间修改也是O(logn)

树状数组

树状数组是前缀和与差分的推广,用于解决 前缀和的修改的问题.

树状数组在实现层面比线段树简单不少, 因为树状数组使用差分思想 而线段树需要lazy标签等操作.

树状数组要求 元素满足: 结合律 与 可差分.

树状数组 使用O(n)时间建表,O(logn)区间查询,O(logn)单点修改.

• 线段树是将数组使用二叉树分为了高度为logn的树 它存放不同的区间信息

• 树状数组是将数组的前缀和分为了最多logn个区间

树状数组建的表比较特殊:

原数组为 arr = [2,3,5,1,4,6,8,9]

我们下标从1开始,因为树状数组需要lowbit运算

• tree[1] = arr[1]

• tree[2] = arr[1..=2]

• tree[3] = arr[3]

• tree[4] = arr[1..=4]

• tree[5] = arr[5]

• tree[6] = arr[5..=6]

\[ tree[n] = \sum_{i = n - lowbit(n) + 1} ^{n} arr[i] \]

• lowbit(n) = i & (-i) ,表示二进制中最低位1所代表的值

比如 tree[6], lowbit(110) = 2, tree[6] = arr[5] + arr[6]

• 区间查询: 我们使用前缀和来查询区间. 假设要求prefix_sum[6], 那么直接 i <- i - lowbit(i) 遍历.

1. lowbit(6) = 2, 6 - 2 = 4 , 取 tree[6]

2. lowbit(4) = 4 , 4 - 4 = 0 , 取 tree[4]

即 prefix_sum[6] = tree[4] + tree[6]

我们实际上是在一次次消耗掉最低位的1,而最多只有logn位 所以O(logn) 时间可以查询 前缀和. 而两个前缀和可以得到区间查询.

• 单点修改: 假设我们要修改 arr[5].

那么取 i <- i + lowbit(i) 遍历.

1. lowbit(5) = 1, 5 + 1 = 6, 取tree[5]

2. lowbit(6) = 2, 6 + 2 = 8, 取tree[6]

3. lowbit(8) = 8, 8 + 8 = 16. 取tree[8]

4. ... 知道 i 超过了n为止.

然后给这些节点都修改即可. 这些区间刚好包含arr[5].

并查集

并查集能很好的处理连通性问题.

并查集可以快速的解决两个问题: 查询与合并.

并查集其实和树结构极其类似 但是: 它更注重于子节点最终属于谁

/// 并查集
pub struct Dsu {
	/// 父节点指针
	parent: Vec<usize>,
	/// 
	rank: Vec<usize>,
}

一个示例

假设有4而城市: 1 2 3 4

一开始每个城市都是独立的 用数组 parent[u]来表示 城市u 的上级

那么并查集在这里的查询就是: parent[u]

而合并操作为: 给定一条道路 比如(1,2) 意味着1与2联通了

图

图有两种元素: G = (V,E)

• 顶点Vertex

• 边Edge

根据边的性质 图可以分为如下几种

图的类型

1. 无向图

边没有方向

2. 有向图

边有方向

3. 加权图

边带有数值

• 特殊图

比如树 二分图

图的性质

1. 度: 这个顶点有相邻的边的数量

2. 路径: 顶点的序列.

3. 连通性: 从任意一个顶点出发 都能通过路径到达其他顶点.

4. 环: 起始和结束于同一个点的路径

抽象为类型

计算机抽象图主要有两个方式

邻接矩阵

一个 \(V \times V\) 的 二维数组.

• 若i到j有边 则(i,j)=权重

• 优点: 查询任意两点是否直接相连 O(1)

• 缺点: 空间复杂度大

邻接表

长度为V的数组 每个元素是一个链表

• 数组索引i对应顶点i,其中的元素链表存放了连向的邻居节点.

• 优点: 空间效率高O(V+E)

• 缺点: 查询两点是否相连需要遍历链表

环

判断有向无环图DAG是一个非常广泛的问题 比如Gentoo的Portage循环依赖发现, Linux内核的一些结构,神经网络的计算图. 所以我们将研究 如何在有向图中判断是否有环.

主流的两个方法是

1. DFS

2. Kahn拓扑排序

DFS

DFS判断有向图里是否有环需要额外维护一个 三状态信息

我们看看下面的情况: 我们发现b虽然被访问了两次 但是是两次不同的DFS访问了b 而不是一次DFS访问了两次b

所以需要维护3个状态: 0 没访问过,1 正在访问,2 访问完了

a ----> b
      ^
	  |
c-----|

字符串

最长重复字符的子串

fn max_substr(s: &str) -> usize {
    if s.len() == 0 {return 0;}
    let s = s.as_bytes();
    let (mut mx,mut l) = (1,0);
    for r in 1..s.len() {
	if s[r] != s[r-1] {
	    l = r;
	} else {
	    mx = mx.max(r - l + 1);
	}
    }
    mx
}

字符串匹配算法

KMP

KMP算法是先预处理一个pattern数组 它记录了: 如果匹配到这没匹配成功 就直接跳转相应的位置.

比如

a b a b a b c
match
a b a b c

我们注意到第一次的abab匹配完后 其实可以直接把ab跳了 注意 不能把abab都跳了.

而KMP算法是求出它的pattern数组 也就是对应跳转多少

a b a b c
match
a b a b

-> 
a b a b c
match
    a b a b

我们发现 当前缀ab和后缀ab相等时可以跳.

所以这个pattern其实就是前缀与后缀的最长相等长度.

我们可以引入前缀函数的概念了

前缀函数的值为 最长的前缀与后缀的相等的长度.

前缀函数算法

KMP的问题转换为了对前缀函数的快速求解问题.

朴素的算法为: 从前往后 和 从后往前匹配

pub fn prefix_func(s: String) {
	let s = s.bytes();
	let len = s.len();
	let mut prefix_func_arr = vec![0;len];
	for i in 0..len {
		let mut max = 0;
		for k in (1..i+1).rev() {
			let prefix = &s[0..k];
			let suffix = &s[i+1-k..i+1];
			if prefix == suffix {
				prefix_func_arr[i] = k;
				break;
			}
		}
	}
}

Manacher算法

在 \(O(N)\) 时间复杂度下 求出以每个位置为回文中心的回文半径.

数学算法

快速幂

用于在 \(\Theta(logn)\)时间计算\(a^n\)的算法.

核心思想为:

将幂按照指数的 二进制表示 分割.

举个例子: 假设我要计算\(3^7\) 普通的方法是\( 3 * 3 * 3 ... * 3\) 需要7次.

如果使用快速幂 只需要计算4次: \(3^2 = 9\) \( 3^3 = 27\) \(3^6 = 729\) \(3^7 = 2187\)

在底下的代码中 base存储的是\(2^k\)次幂 而exp&1筛选出这个幂是否需要被乘进去

/// caculate base^exp
fn fast_pow(mut base: u64, mut exp: u32) -> u64 {
    let mut result = 1;

    while exp > 0 {
		// 如果最低位为1 代表这一位代表的指数需要乘进去
        if exp & 1 == 1 {   
			// result = base
            result *= base;
        }
		// 平方底数
        base *= base;
		// 右移指数
        exp >>= 1; 
    }

    result
}

Berlekamp-Massey

求数列的最短递推式的算法.

问题的定义:

给定一个序列 \(s_0, s_1, s_2, ..., s_{n-1}\)，找到最短的阶的线性递推关系：

\[s_i = \sum_{j=1}^{L} c_j \cdot s_{i-j}\]

其中 \(L\) 是递推式的长度也叫阶 ，\(c_1, c_2, ..., c_L\) 是递推系数。

比如斐波那契是二阶

核心思想：

• 从空递推式开始，逐个处理序列元素

• 当当前递推式无法预测下一个元素时，更新递推式

• 使用之前保存的"最佳失配递推式"来修正当前递推式

• 时间复杂度 \(O(n^2)\)

算法流程：

1. 维护当前递推式 \(C(x)\) 和上一个失配时的递推式 \(B(x)\)

2. 对于每个位置 \(i\)，计算差值 \(\Delta\)（当前递推式预测值与实际值的差）

3. 如果 \(\Delta \neq 0\)，说明当前递推式失配，需要更新

4. 更新时利用 \(B(x)\) 来修正 \(C(x)\)

/// Berlekamp-Massey 算法求最短线性递推
/// 返回递推系数 [c1, c2, ..., cL]
/// 满足 s[i] = c1*s[i-1] + c2*s[i-2] + ... + cL*s[i-L]
fn berlekamp_massey(s: &[i64], modulo: i64) -> Vec<i64> {
    let n = s.len();
    let mut c = vec![0i64]; // 当前递推式
    let mut b = vec![0i64]; // 上一个失配时的递推式
    let mut l = 0;           // 当前递推式长度
    let mut m = 1;           // 距离上次失配的步数
    let mut old_delta = 1;   // 上次失配的delta值
    
    for i in 0..n {
        // 计算当前递推式的预测值
        let mut delta = s[i];
        for j in 1..=l {
            delta = (delta - c[j] * s[i - j] % modulo + modulo) % modulo;
        }
        
        // 如果预测正确 继续下一个
        if delta == 0 {
            m += 1;
            continue;
        }
        
        // 预测失败 需要更新递推式
        let mut d = c.clone();
        
        // 计算修正系数
        let coef = delta * mod_inv(old_delta, modulo) % modulo;
        
        // 扩展当前递推式长度以容纳修正
        if c.len() < b.len() + m {
            c.resize(b.len() + m, 0);
        }
        
        // 用之前的失配递推式修正当前递推式
        for j in 0..b.len() {
            c[j + m] = (c[j + m] - coef * b[j] % modulo + modulo) % modulo;
        }
        
        // 如果当前长度不够好 更新长度和基准递推式
        if 2 * l <= i {
            l = i + 1 - l;
            b = d;
            old_delta = delta;
            m = 1;
        } else {
            m += 1;
        }
    }
    
    c.truncate(l + 1);
    c
}

/// 计算模逆元 (扩展欧几里得)
fn mod_inv(a: i64, m: i64) -> i64 {
    let (mut a, mut m) = (a, m);
    let (mut x0, mut x1) = (1, 0);
    
    while m != 0 {
        let q = a / m;
        let temp = m;
        m = a % m;
        a = temp;
        
        let temp = x1;
        x1 = x0 - q * x1;
        x0 = temp;
    }
    
    (x0 % m + m) % m
}

应用场景：

• 密码学：分析线性反馈移位寄存器(LFSR)

• 编码理论：纠错码的解码

• 竞赛：已知数列前n项求通项公式

• 矩阵快速幂优化：求递推数列第n项

质因数分解

试除法

对n 用2,3,5,7...整除 当除数大于\(\sqrt{n}\)停止.

Pollard Rho算法

最大公因数gcd

欧几里得算法

fn gcd(a: i32, b: i32) -> i32 {
        if b == 0 {
        a
    } else {
        Self::gcd(b, a % b)
    }

这个算法的思想是:

若 a和b有最大公约数

那么

\[ a = qb + r \]

假设

\[ d = gcd(a,b) \]

而

\[ r = a - qb \]

我们假设 a = md , b = nd

则

\[ r = (m - qn) d \]

所以

\[\boxed{d也整除r}\]

所以我们只需要求

\[ gcd(a,r) = gcd(a, a mod b) \]

容斥原理

\[ |\bigcup_{i=1}^{n} A_i| = \sum_{i=1}^{n} |A_i| - \sum_{1 \leq i \< j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k ... + (-1)^{n-1} |A_1 \cap ... \cap A_n| \]

常用的有两个集合的与三个集合的

\[ \begin{align}\begin{aligned} |A \cup B| = |A| + |B| - |A \cap B|\\|A \cup B \cup C| = |A| + |B| + |B| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \end{aligned}\end{align} \]

GF(2)伽罗瓦域

GF(2) 只有两个元素

\[ GF(2) = {0,1} \]

则有

• 加法单位元: 0

• 乘法单位元: 1

• 加法逆元: 1是1 0是0

• 加法: 整数加法后对2取余 也就是XOR

• 乘法: 也就是AND 因为 仅 \(1 \times 1 = 0\)

所以实际上 二进制串 是 \(x \in GF(2)\) 的向量空间

我们记元素为二进制的长为n的向量为 \(GF(2)^n\)

RMQ

区间最大/最小值