学习树链剖分我看过以下博客：
树链剖分原理和实现
树链剖分整理总结
知道大概之后，我以为要多加深记忆的地方：
对于每一个重儿子，其top必然是其父亲的top，并且由于要用其它数据结构（如树状数组，线段树）等来维护，所以一条链在物理上存储是连续的。
那么如何连续起来？其实靠的是dfs1打的标记，一条重链的dfs序号必然连续。
了解这个之后，求u到v之间的某些数值，就可以更好地理解那些辅助的数据结构是如何操纵值的了。比如在树状数组中区间是[a,b]，那么要把[a，b]的值增加k，相当于add(a,k)，add(b+1,-k)。
参考kuangbin的模板，假设是基于点权，查询单点值，修改路径上的点权（HDU 3966 树链剖分+树状数组）
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
#define fi first
#define se second
#define pb push_back
const double eps = 1e-8, PI = acos(-1.0f);
const int inf = 0x3f3f3f3f, maxN = 5e4 + 5;
struct Edge {
int to, next;
} edge[maxN * 2];
int head[maxN], tot;
int top[maxN]; // top[v]即v所在重链的顶端结点
int fa[maxN]; // 父节点
int deep[maxN]; // 深度
int num[maxN]; // num[v] 以v为根的子树结点数
int p[maxN]; // p[v]为v的dfs位置
int fp[maxN]; // 与p相反
int son[maxN]; // 重子编号
int pos;
void init() {
tot = 0;
// 使用bit 编号从1开始
pos = 1;
mst(head, -1);
mst(son, -1);
}
void addEdge(int u, int v) {
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
void dfs1(int u, int pre, int d) {
deep[u] = d;
fa[u] = pre;
num[u] = 1;
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (v != pre) {
dfs1(v, u, d + 1);
num[u] += num[v];
if (son[u] == -1 || num[v] > num[son[u]])
son[u] = v;
}
}
}
void getPos(int u, int sp) {
top[u] = sp;
p[u] = pos++;
fp[p[u]] = u;
if (son[u] == -1)
return;
getPos(son[u], sp);
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (v != son[u] && v != fa[u])
getPos(v, v);
}
}
int bit[maxN];
int n;
int sum(int i) {
int s = 0;
while (i > 0) {
s += bit[i];
i -= i & -i;
}
return s;
}
int add(int i, int x) {
while (i <= n) {
bit[i] += x;
i += i & -i;
}
}
void modify(int u, int v, int val) {
int f1 = top[u], f2 = top[v];
int tmp = 0;
while (f1 != f2) {
if (deep[f1] < deep[f2]) {
swap(f1, f2);
swap(u, v);
}
add(p[f1], val);
add(p[u] + 1, -val);
u = fa[f1];
f1 = top[u];
}
if (deep[u] > deep[v])
swap(u, v);
add(p[u], val);
add(p[v] + 1, -val);
}
int a[maxN];
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int M, P;
while (~scanf("%d%d%d", &n, &M, &P)) {
int u, v;
int C1, C2, K;
char op[10];
init();
rep(i, 1, n + 1)
scanf("%d", &a[i]);
while (M--) {
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
dfs1(1, 0, 0);
getPos(1, 1);
mst(bit, 0);
rep(i, 1, n + 1) {
add(p[i], a[i]);
add(p[i] + 1, -a[i]);
}
while (P--) {
scanf("%s", op);
if (op[0] == 'Q') {
scanf("%d", &u);
printf("%d\n", sum(p[u]));
} else {
scanf("%d%d%d", &C1, &C2, &K);
if (op[0] == 'D')
K = -K;
modify(C1, C2, K);
}
}
}
return 0;
}
基于边权，修改单条边权，查询路径边权最大值（SPOJ QTREE 树链剖分+线段树）
那么，如何解决边权的计算问题呢？我们可以把边看作点。留意到树中节点可以有多条出边，但入边最多只有一条。故而我们可以拿点的序号来唯一表示边。
先根据点的关系完成树链剖分的工作。接着我们根据边在树链剖分时的序号（即dfs序号）操纵线段树即可。我想表达的是，线段树中的区间序号只与dfs1序号有关，它是不需明白点和边的意义的，这里不必想得复杂。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
#define fi first
#define se second
#define sz size()
#define lb lower_bound
#define ub upper_bound
#define pb push_back
const double eps = 1e-8, PI = acos(-1.0f);
const int inf = 0x3f3f3f3f, maxN = 1e4 + 5;
int N, M, T;
// 线段树
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
int seg[maxN << 2];
void push_up(int rt) { seg[rt] = max(seg[rt << 1], seg[rt << 1 | 1]); }
void build(int l, int r, int rt) {
seg[rt] = 0;
if (l == r) return;
int m = (l + r) >> 1;
build(lson);
build(rson);
}
int query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R)
return seg[rt];
int m = (l + r) >> 1;
int ret = 0;
if (L <= m) ret = max(ret, query(L, R, lson));
if (R > m) ret = max(ret, query(L, R, rson));
return ret;
}
void update(int p, int x, int l, int r, int rt) {
if (l == r) {
seg[rt] = x;
return;
}
int m = (r + l) >> 1;
if (p <= m) update(p, x, lson);
else update(p, x, rson);
push_up(rt);
}
// 树链剖分
struct Edge {
int to, next;
} edge[maxN * 2];
int head[maxN], tot;
int top[maxN]; // top[v]即v所在重链的顶端结点
int fa[maxN]; // 父节点
int deep[maxN]; // 深度
int num[maxN]; // num[v] 以v为根的子树结点数
int p[maxN]; // p[v]为v的dfs位置
int fp[maxN]; // 与p相反
int son[maxN]; // 重子编号
int pos;
void init() {
tot = 0;
pos = 0;
mst(head, -1);
mst(son, -1);
}
void addEdge(int u, int v) {
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
void dfs1(int u, int pre, int d) {
deep[u] = d;
fa[u] = pre;
num[u] = 1;
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (v != pre) {
dfs1(v, u, d + 1);
num[u] += num[v];
if (son[u] == -1 || num[v] > num[son[u]])
son[u] = v;
}
}
}
void getPos(int u, int sp) {
top[u] = sp;
p[u] = pos++;
fp[p[u]] = u;
if (son[u] == -1)
return;
getPos(son[u], sp);
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (v != son[u] && v != fa[u])
getPos(v, v);
}
}
// 查询u->v边的max
int findMax(int u, int v) {
int f1 = top[u], f2 = top[v];
int tmp = 0;
while (f1 != f2) {
if (deep[f1] < deep[f2]) {
swap(f1, f2);
swap(u, v);
}
tmp = max(tmp, query(p[f1], p[u], 0, pos - 1, 1));
u = fa[f1];
f1 = top[u];
}
if (u == v) return tmp;
if (deep[u] > deep[v]) swap(u, v);
return max(tmp, query(p[son[u]], p[v], 0, pos - 1, 1));
}
int e[maxN][3];
// CHANGE i ti 修改第i条边的值为ti
// QUERY a b 询问a到b的最大边权
// DONE 结束符号
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
scanf("%d", &T);
while (T--) {
init();
scanf("%d", &N);
rep(i, 0, N - 1) {
scanf("%d%d%d", &e[i][0], &e[i][1], &e[i][2]);
addEdge(e[i][0], e[i][1]);
addEdge(e[i][1], e[i][0]);
}
dfs1(1, 0, 0);
getPos(1, 1);
build(0, pos - 1, 1);
rep(i, 0, N - 1) {
if (deep[e[i][0]] > deep[e[i][1]])
swap(e[i][0], e[i][1]);
update(p[e[i][1]], e[i][2], 0, pos - 1, 1);
}
char op[10];
int u, v;
while (~scanf("%s", op)) {
if (op[0] == 'D') break;
scanf("%d %d", &u, &v);
if (op[0] == 'C')
update(p[e[u - 1][1]], v, 0, pos - 1, 1);
else
printf("%d\n", findMax(u, v));
}
}
return 0;
}
bzoj 1036 修改点权，问u，v路径上的点权之和，点权最大值
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
#define fi first
#define se second
#define sz size()
#define lb lower_bound
#define ub upper_bound
#define pb push_back
const double eps = 1e-8, PI = acos(-1.0f);
const int inf = 0x3f3f3f3f, maxN = 3e4 + 5;
int N, M, T;
// 线段树
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
int big[maxN << 2], sum[maxN << 2];
void push_up(int rt) {
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
big[rt] = max(big[rt << 1], big[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
big[rt] = -inf;
sum[rt] = 0;
if (l == r)
return;
int m = (l + r) >> 1;
build(lson);
build(rson);
push_up(rt);
}
void update(int p, int to, int l, int r, int rt) {
if (l == r) {
sum[rt] = to;
big[rt] = to;
return;
}
int m = (l + r) >> 1;
if (p <= m) update(p, to, lson);
else if (p > m) update(p, to, rson);
push_up(rt);
}
// mode 1求和 2求最大值
int query(int L, int R, int l, int r, int rt, int mode) {
if (L <= l && r <= R) {
if (mode == 1) return sum[rt];
else return big[rt];
}
int m = (l + r) >> 1;
if (mode == 1) {
int ret = 0;
if (L <= m) ret += query(L, R, lson, 1);
if (R > m) ret += query(L, R, rson, 1);
return ret;
} else {
int ret = -inf * 2;
if (L <= m) ret = max(ret, query(L, R, lson, 2));
if (R > m) ret = max(ret, query(L, R, rson, 2));
return ret;
}
}
// 点权 树链剖分
struct Edge { int to, next; } edge[maxN * 2];
int head[maxN], tot;
int top[maxN];
int fa[maxN];
int deep[maxN];
int num[maxN];
int p[maxN];
int fp[maxN];
int son[maxN];
int pos;
void init() { tot = 0; pos = 1; mst(head, -1); mst(son, -1); }
void addEdge(int u, int v) {
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
void dfs1(int u, int pre, int d) {
deep[u] = d;
fa[u] = pre;
num[u] = 1;
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (v == pre) continue;
dfs1(v, u, d + 1);
num[u] += num[v];
if (son[u] == -1 || num[v] > num[son[u]])
son[u] = v;
}
}
void getPos(int u, int sp) {
top[u] = sp;
p[u] = pos++;
fp[p[u]] = u;
if (son[u] == -1) return;
getPos(son[u], sp);
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (v != son[u] && v != fa[u])
getPos(v, v);
}
}
int getMax(int u, int v) {
int f1 = top[u], f2 = top[v];
int tmp = -inf;
while (f1 != f2) {
if (deep[f1] < deep[f2]) {
swap(f1, f2);
swap(u, v);
}
tmp = max(tmp, query(p[f1], p[u], 1, N, 1, 2));
u = fa[f1], f1 = top[u];
}
if (deep[u] > deep[v]) swap(u, v);
return max(tmp, query(p[u], p[v], 1, N, 1, 2));
}
int getSum(int u, int v) {
int f1 = top[u], f2 = top[v];
int s = 0;
while (f1 != f2) {
if (deep[f1] < deep[f2]) {
swap(f1, f2);
swap(u, v);
}
s += query(p[f1], p[u], 1, N, 1, 1);
u = fa[f1], f1 = top[u];
}
if (deep[u] > deep[v]) swap(u, v);
return s += query(p[u], p[v], 1, N, 1, 1);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
scanf("%d", &N);
init();
int u, v;
rep(i, 0, N - 1) {
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
dfs1(1, 0, 0);
getPos(1, 1);
build(1, N, 1);
int w;
rep(i, 1, N + 1) {
scanf("%d", &w);
update(p[i], w, 1, N, 1);
}
scanf("%d", &T);
char op[10];
while (T--) {
scanf("%s %d %d", op, &u, &v);
if (op[1] == 'M')
printf("%d\n", getMax(u, v));
else if (op[1] == 'S')
printf("%d\n", getSum(u, v));
else
update(p[u], v, 1, N, 1);
}
return 0;
}
网友评论