浅谈树链剖分 F&Q

　　这是一篇迟来的博客，由于我懒得写文章，本篇以两个问题阐述笔者对树链剖分的初步理解。

Q1：树链剖分解决什么问题？

　　树链剖分，就是把一棵树剖分成若干连续的链，将这些链里的数据映射在线性数组上维护。比方说我们想要维护树上任意两点间的lca，或者支持一段路径或一棵子树的修改和查询，都可以用树链剖分来解决。

Q2：树链剖分是什么原理？

　　以经典的重链剖分为例，列举笔者认为是树剖核心的两个基本数据结构性质：

　　1、树剖序：树剖所维护的几个基本信息如dfn（时间戳）、size（子树大小）、fa（树上父亲），在这里不过多赘述。这里只分析基于son（重儿子）所得出的树剖序的本质。

　　我们在打时间戳遍历原树的时候，实际上做了遍特殊的dfs，这个dfs以优先遍历重儿子为原则，对应的dfs序实际上就是树剖序。换言之，树剖序是一种特殊的dfs序，它首先符合dfs序的特征，如“u的子树在树剖序里是一段连续区间”这样的性质支持我们可以用区间数据结构（线段树）来维护子树的信息。

　　同时，树剖序有自己的独特性质。相信能看到这篇博客的同学都对所谓“重链”有了了解：每条重链都是由叶子结点沿返祖边指向祖先方向的一条树链，它上面除了最浅的一个点以外的所有结点都是对应祖先的重儿子。两条重链之间通过一条轻边衔接。既然我们优先遍历重儿子，每段重链在树剖序上都是一段连续的区间：而每个节点要么是重儿子（在重链上），要么是某条重链的起点；那么每个节点都一定且仅属于某条重链。所以我们按树剖序得到的线性数组就是由若干条重链拼成的，我们可以在其上用维护区间的方法便可以维护整棵树的信息。

　　2、重链的优越性

　　那么，树链剖分的高效性何在？首先，我们记录每个点所在重链的链头，从某一点转移到链头的复杂度是O(1)的。修改、查询每段树链用线段树log级维护。而我们需要沿轻边跳跃多少次就可以覆盖整条路径呢？

　　引理：任一点到根节点的轻边最多有log条。

　　这实际上是个很显然的性质：最坏的情况就是每条边都是轻边，每次从轻儿子v跳到u，由于size[v] < size[son[u]]，子树的大小便至少会增加一倍，那么最多会增加log次，这就是我们要按轻重剖分的原因。

　　于是树链剖分每次询问都1最坏时间为O(logn*logn)，实际上很难有极端数据来卡到这个限度，一般还是很优秀的。（笔者用树链剖分打出的lca板子居然跑得和倍增一样快）

　　至此树剖的整体思路已经明了，我们在剖分出的线性区间内架起一棵线段树来维护树上信息即可。下面附上我的树剖代码，码风应该比较清爽，其中线段树的写法也是从大佬那里抄来的精华。希望对各位学习树剖的同学有所帮助。

#include <iostream>
#include <cctype>
#include <cstdio>
#define maxn 100010
#define BUG putchar('*')
using namespace std;
template <typename T>
void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + (ch ^ 48);
ch = getchar();
}
x *= f;
return;
}
int mod;
int head[maxn], top;
int n, m, root;
int val[maxn], w[maxn]; //共计三个数据数组：原始值、树剖序对应值和线段树
struct E {
int to, nxt;
} edge[maxn << 1];
inline void insert(int u, int v) {
edge[++top] = (E) {v, head[u]};
head[u] = top;
}
namespace segement_tree { //线段树部分
#define lc (nd<<1)
#define rc ((nd<<1)|1)
struct node {
int val, len;
inline friend node operator + (node a, node b) {
return (node) {(a.val + b.val) % mod, a.len + b.len};
}
} data[maxn << 2];
int tag[maxn << 2]; //lazy_tag只维护简单的加减
inline node operator * (node a, int b) {
return (node) {a.val + (b * a.len) % mod, a.len};
}
inline void put_tag(int nd, int del) {
data[nd] = data[nd] * del;
tag[nd] = tag[nd] + del;
}
inline void update(int nd) {
data[nd] = data[lc] + data[rc];
}
inline void push_down(int nd) { //下推，同时释放当前节点的tag信息
put_tag(lc, tag[nd]);
put_tag(rc, tag[nd]);
tag[nd] = 0;
}
void build(int nd, int l, int r) {
if (l == r) {
data[nd] = (node) {w[l], 1};
return;
}
int mid = (l + r) >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
update(nd);
}
void modify(int nd, int l, int r, int ql, int qr, int del) {
if (l >= ql && r <= qr) {
put_tag(nd, del);
return;
} else if (l > qr || r < ql)
return;
push_down(nd);
int mid = (l + r) >> 1;
modify(lc, l, mid, ql ,qr, del);
modify(rc, mid + 1, r, ql, qr, del);
update(nd);
}
int query(int nd, int l, int r, int ql, int qr) {
if (l >= ql && r <= qr) {
return data[nd].val;
} else if (l > qr || r < ql)
return 0;
push_down(nd);
int mid = (l + r) >> 1;
return (query(lc, l, mid, ql, qr) + query(rc, mid + 1, r, ql, qr)) % mod;
}
}
namespace Divtree {
using namespace segement_tree; //我感觉这个写法挺好的，表明了树剖对线段树的调用关系
int ftop[maxn], f[maxn], size[maxn], son[maxn], d[maxn];
int timer;
int id[maxn];//树剖序
void dfs1(int u, int pre) { //第一次dfs，维护节点的深度、父亲、重量以及重儿子信息
f[u] = pre;
size[u] = 1;
d[u] = d[pre] + 1;
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if (v == pre) continue;
dfs1(v, u);
size[u] += size[v];
if (size[v] > size[son[u]])
son[u] = v;
}
}
void dfs2(int u, int tp) { //按树剖序遍历，把树上信息剖分在线性数组上
ftop[u] = tp;
id[u] = ++timer;
w[timer] = val[u]; //拷贝
if (son[u])
dfs2(son[u], tp); //搭建当前重链
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if (v != f[u] && v != son[u])
dfs2(v, v); //沿轻边搭建新的重链
}
}
void init() {
dfs1(root, root);
dfs2(root, root);
build(1, 1, n);
}
inline void Msub(int u, int del) {
modify(1, 1, n, id[u], id[u] + size[u] - 1, del);
}
inline int Qsub(int u) {
return query(1, 1, n, id[u], id[u] + size[u] - 1) % mod;
}
void Mrange(int u, int v, int del) {
while (ftop[u] != ftop[v]) {
if (d[ftop[u]] < d[ftop[v]])
swap(u, v);
modify(1, 1, n, id[ftop[u]], id[u], del);
u = f[ftop[u]];
}
if (d[u] > d[v]) swap(u, v);
modify(1, 1, n, id[u], id[v], del);
}
int Qrange(int u, int v) {
int ans = 0;
while (ftop[u] != ftop[v]) {
if (d[ftop[u]] < d[ftop[v]])
swap(u, v);
ans = (ans + query(1, 1, n, id[ftop[u]], id[u])) % mod;
u = f[ftop[u]];
}
if (d[u] > d[v]) swap(u, v);
ans = (ans + query(1, 1, n, id[u], id[v])) % mod;
return ans;
}
} using namespace Divtree;
int main() {
read(n), read(m), read(root), read(mod);
int u, v, del;
for (int i = 1; i <= n; ++i)
read(val[i]);
for (int i = 1; i < n; ++i) {
read(u), read(v);
insert(u, v), insert(v, u);
}
init();
register char ch;
while (m--) {
ch = getchar();
while (!isdigit(ch)) ch = getchar();
if (ch == '1') {
read(u), read(v), read(del);
Mrange(u, v, del);
} else if (ch == '2') {
read(u), read(v);
printf("%d\n", Qrange(u, v));
} else if (ch == '3') {
read(u), read(del);
Msub(u, del);
} else {
read(u);
printf("%d\n", Qsub(u));
}
}
return 0;
}

巴特西

浅谈树链剖分 F&Q

最新文章

热门文章