一、简介
长链剖分是一种基于动态规划思想的算法，用于解决静态区间查询的问题。它将一条长链分为若干个短链，使得查询的时间复杂度降至 O(log n)，解决了静态区间查询的效率问题。
长链剖分可以被用于很多静态区间查询的场景，比如线段树、树链剖分、主席树等。
二、核心思想
长链剖分的核心思想是将一条较长的链分为若干个较短的链，使得查询的时间复杂度降低到 O(log n)。
具体实现过程中，我们可以将一条长链分割成 k 条较短的链，每条链的长度为 O(log n)，并建立一个虚树，虚树是由长链上的一些重链、轻链以及一些根据 LCA（最近公共祖先）得到的节点组成的一棵树。
每个节点都对应着一条较短的链，较短链上的信息可以预处理，查询的时候只需要暴力查询所有较短链上的信息即可。
//代码示例
void dfs(int u, int fa, int &k) {
size[u] = 1;
for(int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].to;
if(v == fa) continue;
dfs(v, u, k);
size[u] += size[v];
if(size[v] > size[son[u]]) son[u] = v;
}
if(size[u] > size[son[u]] + 1) //重链
c[++k] = u;
}
三、详细实现
1、建虚树
在实现长链剖分之前，需要先建立虚树。虚树是一棵由长链上的一些重链、轻链以及一些根据 LCA（最近公共祖先）得到的节点组成的一棵树。
具体操作如下：
1）将整个链缩成点。将一条长链缩成一个点作为虚树的根节点，则原先的长链上面所有的点成为虚树上的叶子节点。
2）可以根据 LCA 算法，将每一个询问中的区间变成一颗虚子树，其中 LCA 到询问两端的点的路径就是虚子树上的重链，而非这些点到 LCA 的路径就是轻链。
//代码示例
void dfs(int u, int fa, int &k) {
size[u] = 1;
for(int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].to;
if(v == fa) continue;
dfs(v, u, k);
size[u] += size[v];
if(size[v] > size[son[u]]) son[u] = v;
}
if(size[u] > size[son[u]] + 1) //重链
c[++k] = u;
}
void dfs2(int u, int fa, int top) {
id[u] = ++cnt;
tp[u] = top;
rk[cnt] = u;
if(son[u]) dfs2(son[u], u, top);
for(int i = head[u]; ~i; i = e[i].nxt)
if(e[i].to != fa && e[i].to != son[u]) dfs2(e[i].to, u, e[i].to);
}
void build(int L, int R, int rt) {
if(L == R) {
tr[rt].push_back(p[rk[L]]);
return;
}
int mid = (L + R) >> 1;
build(L, mid, ls(rt)); build(mid + 1, R, rs(rt));
merge(tr[ls(rt)].begin(), tr[ls(rt)].end(), tr[rs(rt)].begin(), tr[rs(rt)].end(), back_inserter(tr[rt]));
}
2、长链剖分
有了虚树之后，就可以进行长链剖分了。可以按照以下步骤进行：
1）根据每个节点的子树大小，判断重儿子重链，轻儿子轻链。
2）每次查询的时候从查询区间两个端点向上走，直到走到同一条链上，查询沿途链上的信息。
代码实现如下：
//代码示例
struct node {
int l, r;
LL sum;
node() {}
node(int l, int r, LL sum): l(l), r(r), sum(sum) {}
};
vectorT[maxn << 2];
void query(int x, int y, int Lim, int u, int fa, vector
&v) {
if(x > y || x > Lim) return;
if(y <= Lim) {
auto it1 = lower_bound(T[u].begin(), T[u].end(), node(x, -1, -1));
auto it2 = upper_bound(T[u].begin(), T[u].end(), node(y, -1, -1));
for(auto it = it1; it != it2; it++) v.push_back(*it);
return;
}
if(tp[x] == tp[y]) {
if(id[x] > id[y]) swap(x, y);
auto it1 = lower_bound(T[u].begin(), T[u].end(), node(id[x], -1, -1));
auto it2 = upper_bound(T[u].begin(), T[u].end(), node(id[y], -1, -1));
for(auto it = it1; it != it2; it++) v.push_back(*it);
return;
}
if(dep[tp[x]] < dep[tp[y]]) swap(x, y);
auto it1 = lower_bound(T[u].begin(), T[u].end(), node(id[tp[x]], -1, -1));
auto it2 = upper_bound(T[u].begin(), T[u].end(), node(id[x], -1, -1));
for(auto it = it1; it != it2; it++) v.push_back(*it);
query(fa, fa, Lim, u, fa, v);
}
四、优化
在实际应用过程中，有若干优化方法可以减小长链剖分的常数和复杂度，包括但不限于：
1）将长链剖分和主席树结合使用，可以进一步优化空间；
2）对于一些复杂的边权计算场景，可以先对边权进行预处理，以减小边权计算的复杂度；
3）使用同余定理等其他技巧来加速。
五、总结
长链剖分是一种重要的静态区间查询算法，可以有效地提高查询效率。通过对长链剖分的实现及优化，我们可以更加高效地解决一些静态区间查询的问题。
