分治的延伸应用

应用场景

优化合并

假设将两个规模 \(\frac{n}{2}\) 的信息合并为 \(n\) 的时间复杂度为 \(f(n)\)，用主定理分析时间复杂度 \(T(n) = 2 \times T(\frac{n}{2}) + f(n)\)。

能直观的看出优化程度还是很大的。

归并排序中 \(f(n) = O(n)\)，则 \(T(n) = O(n \log n)\)。

特别的当 \(f(n) = O(n^k),k \ge 2\) 时，我们通常不会使用分治，因为无法优化时间复杂度。

优化合并通常应用于哈夫曼树、线段树。

优化计数

我们对长度为 \(n\) 的序列 \(\{a_n\}\) 统计有多少对 \((i,j)\)，使得 \(i < j\) 且 \(a_i > a_j\)。

可以使用分治求解 \([l,r]\) 一段内逆序对数。

我们令 \(\text{mid} = \frac{l + r}{2}\)，分别处理 \([l,\text{mid}]\) 和 \([\text{mid},r]\) 即可。

代码实现的注意事项：

1. 特判分治的递归边界。

2. 若用到临时数组，确保其得到清空，切勿盲目 \(\text{memset}\)。

倍增法

\(\text{RMQ}\) 是英文 \(\text{Range Maximum/Minimum Query}\) 的缩写，表示区间最大（最小）值。

而 \(\text{ST}\) 表是用于解决可重复贡献问题的数据结构。

记 \(f(l, r)\) 为 \([l, r]\) 这个区间的答案，可重复贡献问题就是对所有 \(R \ge L\)，\(f(l, r)\) 可表示为 \(f(l, R)\) 与 \(f(L, r)\) 的合并。

考虑一个 \(\text{RMQ}\) 问题：

给定 \(n\) 个数，有 \(m\) 个询问，对于每个询问你需要回答区间 \([l, r]\) 中的最大值。

令 \(f(i, j)\) 表示区间 \([i, i + 2^j + 1]\) 的最大值，显然 \(f(i, 0) = a_i\)。

状态转移方程为：

对于每个询问 \([l, r]\)，我们把它分成两个部分：\(f(l, l + 2^s - 1)\) 与 \(f(r - 2^s + 1, r)\)，其中 $s = \left \lfloor \log_2 (r - l + 1) \right \rfloor $。

两个部分的结果的较大值就是答案。

建议预处理对数数组：\(\texttt{Log}_1 = 0\)，\(\texttt{Log}_i = \texttt{Log}_{\left \lfloor \frac{i}{2} \right \rfloor} + 1\)，时间复杂度 \(O(n)\)。

除了 \(\text{RMQ}\) 以外，还有其他的“可重复贡献问题”，例如“区间按位和”、“区间按位或”、“区间 \(\text{GCD}\)”，\(\text{ST}\) 表都能高效解决。

\(\text{ST}\) 表维护区间 \(\text{GCD}\) 的时间复杂度预处理 \(O(n \times (\log n + \log w))\)，单次查询 \(O(\log w)\)，其中 \(w\) 是值域。

最近公共祖先 LCA

定义

最近公共祖先简称 \(\text{LCA}\)（\(\text{Lowest Common Ancestor}\)）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。
为了方便，我们记某点集 \(S=\{v_1,v_2,\ldots,v_n\}\) 的最近公共祖先为 \(\text{LCA}(v_1,v_2,\ldots,v_n)\) 或 \(\text{LCA}(S)\)。

性质

本节 性质 部分内容翻译自 wcipeg，并做过修改。

1. \(\text{LCA}(\{u\})=u\)；
2. \(u\) 是 \(v\) 的祖先，当且仅当 \(\text{LCA}(u,v)=u\)；
3. 如果 \(u\) 不为 \(v\) 的祖先并且 \(v\) 不为 \(u\) 的祖先，那么 \(u,v\) 分别处于 \(\text{LCA}(u,v)\) 的两棵不同子树中；
4. 前序遍历中，\(\text{LCA}(S)\) 出现在所有 \(S\) 中元素之前，后序遍历中 \(\text{LCA}(S)\) 则出现在所有 \(S\) 中元素之后；
5. 两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先，即 \(\text{LCA}(A\cup B)=\text{LCA}(\text{LCA}(A), \text{LCA}(B))\)；
6. 两点的最近公共祖先必定处在树上两点间的最短路上；
7. \(d(u,v)=h(u)+h(v)-2h(\text{LCA}(u,v))\)，其中 \(d\) 是树上两点间的距离，\(h\) 代表某点到树根的距离。

求法

朴素算法

过程

可以每次找深度比较大的那个点，让它向上跳。显然在树上，这两个点最后一定会相遇，相遇的位置就是想要求的 \(\text{LCA}\)。
或者先向上调整深度较大的点，令他们深度相同，然后再共同向上跳转，最后也一定会相遇。

性质

朴素算法预处理时需要 \(\text{dfs}\) 整棵树，时间复杂度为 \(O(n)\)，单次查询时间复杂度为 \(\Theta(n)\)。如果树满足随机性质，则时间复杂度与这种随机树的期望高度有关。

倍增算法

过程

倍增算法是最经典的 \(\text{LCA}\) 求法，他是朴素算法的改进算法。通过预处理 \(\text{fa}_{x,i}\) 数组，游标可以快速移动，大幅减少了游标跳转次数。\(\text{fa}_{x,i}\) 表示点 \(x\) 的第 \(2^i\) 个祖先。\(\text{fa}_{x,i}\) 数组可以通过 \(\text{dfs}\) 预处理出来。

现在我们看看如何优化这些跳转：
在调整游标的第一阶段中，我们要将 \(u,v\) 两点跳转到同一深度。我们可以计算出 \(u,v\) 两点的深度之差，设其为 \(y\)。通过将 \(y\) 进行二进制拆分，我们将 \(y\) 次游标跳转优化为「\(y\) 的二进制表示所含 1 的个数」次游标跳转。
在第二阶段中，我们从最大的 \(i\) 开始循环尝试，一直尝试到 \(0\)（包括 \(0\)），如果 \(\text{fa}_{u,i}\not=\text{fa}_{v,i}\)，则 \(u\gets\text{fa}_{u,i},v\gets\text{fa}_{v,i}\)，那么最后的 \(\text{LCA}\) 为 \(\text{fa}_{u,0}\)。

性质

倍增算法的预处理时间复杂度为 \(O(n \log n)\)，单次查询时间复杂度为 \(O(\log n)\)。
另外倍增算法可以通过交换 fa 数组的两维使较小维放在前面。这样可以减少 \(\text{cache miss}\) 次数，提高程序效率。

例题：HDU 2586 How far away? 树上最短路查询。

可先求出 \(\text{LCA}\)，再结合性质 \(7\) 进行解答。也可以直接在求 \(\text{LCA}\) 时求出结果。

参考代码：

#include <cstdio>
#include <cstring>
#include <vector>

#define MXN 40005
using namespace std;
std::vector<int> v[MXN];
std::vector<int> w[MXN];

int fa[MXN][31], cost[MXN][31], dep[MXN];
int n, m;
int a, b, c;

// dfs，用来为 lca 算法做准备。接受两个参数：dfs 起始节点和它的父亲节点。
void dfs(int root, int fno) {
  // 初始化：第 2^0 = 1 个祖先就是它的父亲节点，dep 也比父亲节点多 1。
  fa[root][0] = fno;
  dep[root] = dep[fa[root][0]] + 1;
  // 初始化：其他的祖先节点：第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第
  // 2^(i-1) 的祖先节点。
  for (int i = 1; i < 31; ++i) {
    fa[root][i] = fa[fa[root][i - 1]][i - 1];
    cost[root][i] = cost[fa[root][i - 1]][i - 1] + cost[root][i - 1];
  }
  // 遍历子节点来进行 dfs。
  int sz = v[root].size();
  for (int i = 0; i < sz; ++i) {
    if (v[root][i] == fno) continue;
    cost[v[root][i]][0] = w[root][i];
    dfs(v[root][i], root);
  }
}

// lca。用倍增算法算取 x 和 y 的 lca 节点。
int lca(int x, int y) {
  // 令 y 比 x 深。
  if (dep[x] > dep[y]) swap(x, y);
  // 令 y 和 x 在一个深度。
  int tmp = dep[y] - dep[x], ans = 0;
  for (int j = 0; tmp; ++j, tmp >>= 1)
    if (tmp & 1) ans += cost[y][j], y = fa[y][j];
  // 如果这个时候 y = x，那么 x，y 就都是它们自己的祖先。
  if (y == x) return ans;
  // 不然的话，找到第一个不是它们祖先的两个点。
  for (int j = 30; j >= 0 && y != x; --j) {
    if (fa[x][j] != fa[y][j]) {
      ans += cost[x][j] + cost[y][j];
      x = fa[x][j];
      y = fa[y][j];
    }
  }
  // 返回结果。
  ans += cost[x][0] + cost[y][0];
  return ans;
}

void Solve() {
  // 初始化表示祖先的数组 fa，代价 cost 和深度 dep。
  memset(fa, 0, sizeof(fa));
  memset(cost, 0, sizeof(cost));
  memset(dep, 0, sizeof(dep));
  // 读入树：节点数一共有 n 个，查询 m 次，每一次查找两个节点的 lca 点。
  scanf("%d %d", &n, &m);
  // 初始化树边和边权
  for (int i = 1; i <= n; ++i) {
    v[i].clear();
    w[i].clear();
  }
  for (int i = 1; i < n; ++i) {
    scanf("%d %d %d", &a, &b, &c);
    v[a].push_back(b);
    v[b].push_back(a);
    w[a].push_back(c);
    w[b].push_back(c);
  }
  // 为了计算 lca 而使用 dfs。
  dfs(1, 0);
  for (int i = 0; i < m; ++i) {
    scanf("%d %d", &a, &b);
    printf("%d\n", lca(a, b));
  }
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) Solve();
  return 0;
}

Tarjan 算法

过程

\(\text{Tarjan}\) 算法是一种 离线算法，需要使用并查集记录某个结点的祖先结点。做法如下：

1. 首先接受输入边（邻接链表）、查询边（存储在另一个邻接链表内）。查询边其实是虚拟加上去的边，为了方便，每次输入查询边的时候，将这个边及其反向边都加入到 queryEdge 数组里。
2. 然后对其进行一次 DFS 遍历，同时使用 visited 数组进行记录某个结点是否被访问过、parent 记录当前结点的父亲结点。
3. 其中涉及到了 回溯思想，我们每次遍历到某个结点的时候，认为这个结点的根结点就是它本身。让以这个结点为根节点的 DFS 全部遍历完毕了以后，再将这个结点的根节点设置为这个结点的父一级结点。
4. 回溯的时候，如果以该节点为起点，queryEdge 查询边的另一个结点也恰好访问过了，则直接更新查询边的 \(\text{LCA}\) 结果。
5. 最后输出结果。

性质

\(\text{Tarjan}\) 算法需要初始化并查集，所以预处理的时间复杂度为 \(O(n)\)。

朴素的 \(\text{Tarjan}\) 算法处理所有 \(m\) 次询问的时间复杂度为 \(O(m \alpha(m+n, n) + n)\)。但是 Tarjan 算法的常数比倍增算法大。存在 \(O(m + n)\) 的实现。

注意：

并不存在「朴素 \(\text{Tarjan LCA}\) 算法中使用的并查集性质比较特殊，单次调用 find() 函数的时间复杂度为均摊 \(O(1)\)」这种说法。

以下的朴素 \(\text{Tarjan}\) 实现复杂度为 \(O(m \alpha(m+n, n) + n)\)。如果需要追求严格线性，可以参考 Gabow 和 Tarjan 于 1983 年的论文。其中给出了一种复杂度为 \(O(m + n)\) 的做法。

例题

例题 Luogu P3379【模板】最近公共祖先（LCA）。

参考代码：

#include<iostream>
using namespace std;
#define MAXN 500010

struct node {
    int t, nex;
} e[MAXN << 1]; 
int head[MAXN], tot;
int n, m, s;
int depth[MAXN], fa[MAXN][30], lg[MAXN];

void add(int x, int y) {
	e[++ tot].t = y;
	e[tot].nex = head[x];
	head[x] = tot;
	return;
}

void dfs(int now, int fath) {
	fa[now][0] = fath; depth[now] = depth[fath] + 1;
	for(int i = 1; i <= lg[depth[now]]; i ++)
		fa[now][i] = fa[fa[now][i - 1]][i - 1];
	for(int i = head[now]; i; i = e[i].nex)
		if(e[i].t != fath) dfs(e[i].t, now);
	return;
}

int LCA(int x, int y) {
	if(depth[x] < depth[y]) swap(x, y);
	while(depth[x] > depth[y])
		x = fa[x][lg[depth[x] - depth[y]] - 1];
	if(x == y) return x;
	for(int k = lg[depth[x]] - 1; k >= 0; k --)
		if(fa[x][k] != fa[y][k]) x = fa[x][k], y = fa[y][k];
	return fa[x][0];
}

int main() {
	cin >> n >> m >> s; 
	for(int i = 1, x, y; i <= n - 1; i ++) {
		cin >> x >> y;
		add(x, y); add(y, x);
	}
	// 预处理 log_2(i) + 1 的值 
	for(int i = 1; i <= n; i ++)
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
	dfs(s, 0);
	for(int i = 1, x, y; i <= m; i ++) {
		cin >> x >> y;
		cout << LCA(x, y) << "\n";
	}
	return 0;
}