C++ 前缀和与差分、倍增与分治
AndyPomeloMars
·
·
个人记录
前缀和
定义
数列的前 n 项的和，它是一种重要的预处理方式，能大大降低 查询 的时间复杂度
操作
一般来讲，我们会 预处理 一个数组。对数组中每个元素，我们记录从 起始 到 该元素对应下标 / 状态 所有数字的总和
一维前缀和
给定一个长度为 n 的数组 a，预处理一个 f 数组作为前缀和。那么：
f_i = \sum_{j = 1}^{i} a_j = a_1 + a_2 + ... + a_i
实现方式：
f[i] = f[i - 1] + a[i]
二维前缀和
给定一个 n × m 的数组 a，预处理一个 f 二维数组作为前缀和。那么：
f_{i,j} = \sum_{k = 1}^{i} \sum_{l = 1}^{j} a_{k, l} = a_{1, 1} + ... + a_{1, j} + a_{2, 1} + ... + a_{i, j}
实现方式：
f[i][j] = f[i - 1][j] + f[i][j - 1] + f[i - 1][j - 1] + a[i][j]
差分
定义
前缀和的逆运算，能大大降低 多次修改 但 最终只有一次查询 的时间复杂度
操作
一般来讲，我们会 预处理 一个数组。对数组中每个元素，我们记录 该元素对应下标 / 状态 代表的值与其 之前一个 的值的差值
对一个长度为 n 的数组 a，我们对其建立差分数组 f，那么：
f_i =
\left\{
\begin{matrix}
a_1, i = 1
\\
a_i - a_{i - 1}, 2 \leq i \leq n
\end{matrix}
\right.
倍增
定义
倍增，顾名思义就是翻倍，它能够使线性的处理 O(n) 转化为对数级的处理 O(\log n)，大大地优化时间复杂度
本质
对于一种问题 f(x)，通过计算 f^1(x), f^2(x), f^4(x), ..., f^(2^k)(x) 来加速求解 f^n(x)
对于某些规模为 n 的问题，它的答案可以由若干个规模为 2 的幂的子问题合并而来
ST表
定义
ST 表是用于解决 可重复贡献问题（可重复贡献问题：是指对于运算 \operatorname{opt}，满足 x \operatorname{opt} x = x，则对应的区间询问就是一个可重复贡献问题。例如，最大值有 \max(x, x) = x，gcd 有 \operatorname{gcd}(x, x) = x，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次，这是我们所不愿意看到的。另外，\operatorname{opt} 还必须满足结合律才能使用 ST 表求解） 的数据结构。可以求解类似于：给定 n 个数，有 m 个询问，对于每个询问，你需要回答区间 [l,r] 中的最大值
分析
ST 表基于 倍增 思想，可以做到 O(n\log n) 预处理，O(1) 回答每个询问，但是不支持修改操作
基于倍增思想，我们考虑如何求出区间最大值。可以发现，如果按照一般的倍增流程，每次跳 2 ^ i 步的话，询问时的复杂度仍旧是 O(\log n)，并没有比线段树更优，反而预处理一步还比线段树慢
我们发现 \max(x, x) = x，也就是说，区间最大值是一个具有「可重复贡献」性质的问题。即使用来求解的预处理区间有重叠部分，只要这些区间的并是所求的区间，最终计算出的答案就是正确的
如果手动模拟一下，可以发现我们能使用至多两个预处理过的区间来覆盖询问区间，也就是说询问时的时间复杂度可以被降至 O(1)，在处理有大量询问的题目时十分有效
预处理部分
令 f(i, j) 表示区间 [i, i + 2 ^ j - 1] 的最大值。
显然 f(i, 0) = a_i。
根据定义式，第二维就相当于倍增的时候「跳了 2 ^ j - 1 步」，依据倍增的思路，写出状态转移方程：f(i, j) = \max(f(i, j - 1), f(i + 2 ^ {j - 1}, j - 1))
查询
对于每个询问 [l,r]，我们把它分成两部分：[l, l + 2 ^ s - 1] 与 [r - 2 ^ s + 1, r]，其中 s=\left\lfloor\log_2(r - l + 1)\right\rfloor。两部分的结果的最大值就是回答
结论
根据上面对于「可重复贡献问题」的论证，由于最大值是「可重复贡献问题」，重叠并不会对区间最大值产生影响。又因为这两个区间完全覆盖了 [l,r]，可以保证答案的正确性。
分治
定义
对于任意一层，如果知道了底下一层的答案，可以把分治出的两个问题的答案合并成当前层的答案
分治法一共有两步，依次是：「如何把当前问题划分成更小的问题」，这一步是「分」；「如何把小问题的答案合并成大问题的答案」，这一步是「合」
定理
概念
对规模为 T(n) = aT(\frac{n}{b}) + f(n) 的问题求解的时间复杂度满足。则有：
-
若存在 \varepsilon > 0 满足 f(n) = O(n ^ {\log_b(a - \varepsilon)})，则 T(n) = O(n ^ {\log_ba})
-
若 f(n) = O(n ^ {\log_ba} \log^k n)，则有 T(n) = O(n ^ {\log_ba} \log ^ {k + 1} n)
-
若存在 \varepsilon > 0 满足 f(n) = O(n^{\log_b(a - \varepsilon)})，则 T(n) = O(f(n))
分析
对于一个规模为 n 的问题求解，把问题分成 b 个子问题，求解 b 个子问题的总用时是 aT(\frac{n}{b})，合并 b 个子问题的用时是 f(n)，考察此时的复杂度
应用时，把 f(n) 写成大 O 符号里的最简形式，然后比较这一形式和 n ^ {\log_ba} 的大小关系，三条定理依次对应大于、等于、小于的情况