做法
关于树链剖分我也不知道该怎么讲了,有许多博客比我讲得好,如果你是还没有学习树链剖分的同学的话,在这里安利博客:
(这里指的是轻重链剖分)
这里总结一下:
适用情况
对于一条路径上的值进行修改
查询一条路径上的一些具有可以进行区间维护的性质的东西(比如求和,最大值)
额外的例子:
查询一条路径中的元素种类总数
查询一条路径中大于一个给定的值的数的个数(树链剖分后套权值线段树 or 主席树)
查询路径中第大的数
对于一棵子树中的值进行修改
查询一棵子树中的一些具有可以进行区间维护的性质的东西(比如求和,最大值)
上面四种是最裸的树链剖分。直接上树链剖分加线段树即可。
算法复杂度:
对于路径上的更新权值/求和的时间复杂度是O()。
因为重链的条数不超过条(一般的话数量可能远远低于这个值),每次线段树维护的时间复杂度是:O()的,所以时间复杂度是O的。
子树修改/查询时间复杂度:O,很明显,因为后编号是连续的,时间复杂度就是线段树做区间查询/修改的复杂度
如何构造一棵树使得轻重链剖分后重链条数达到
完全二叉树即可。你可以自己画一棵完全二叉树,然后你就会发现重链很多,但是因为是完全二叉树,那它的深度也不会很深,所以基本上卡不死轻重链剖分。
因为这是一篇题解,所以放上这一题的代码吧。
#include <bits/stdc++.h> using namespace std; #define int long long int n, root, m, now = 0; int start[100005], dfn_id[100005]; struct tree { int siz, son; int data, fa; int deep, dfn, tp; int rs; } node[100005]; struct Tree { int l, r, sum, laz; } T[500005]; struct road { int u, v; } r[500005]; int DFS1(int x, int from) { node[x].deep = node[from].deep + 1; node[x].siz = 1, node[x].son = 0; node[x].fa = from; for (int i = start[x]; i <= m && r[i].u == x; i++) { int to = r[i].v; if (!node[to].deep) { int v; v = DFS1(to, x); if (v > node[node[x].son].siz) node[x].son = to; node[x].siz += v; } } return node[x].siz; } int DFS2(int x, int top) { node[x].tp = top; node[x].dfn = ++now; dfn_id[now] = x; node[x].rs = now; if (node[x].son != 0) node[x].rs = max(DFS2(node[x].son, top), node[x].rs); for (int i = start[x]; i <= m && r[i].u == x; i++) { int to = r[i].v; if (!node[to].dfn && to != node[x].fa && to != node[x].son) node[x].rs = max(DFS2(to, to), node[x].rs); } return node[x].rs; } void build_tree(int x, int l, int r) { T[x].l = l, T[x].r = r; T[x].laz = 0; if (T[x].l == T[x].r) { T[x].sum = node[dfn_id[l]].data; return; } int mid = (l + r) >> 1; build_tree(x << 1, l, mid); build_tree(x << 1 | 1, mid + 1, r); T[x].sum = T[x << 1].sum + T[x << 1 | 1].sum; } int cmp(road A, road B) { return A.u < B.u; } void ad(int x, int k) { T[x].sum += (T[x].r - T[x].l + 1) * k; T[x].laz += k; } int pushdown(int x) { if (T[x].laz == 0) return 0; ad(x << 1, T[x].laz); ad(x << 1 | 1, T[x].laz); T[x].laz = 0; return 0; } int change(int x, int l, int r, int k) { if (T[x].l >= l && T[x].r <= r) { ad(x, k); return 0; } pushdown(x); int mid = (T[x].l + T[x].r) >> 1; if (l <= mid) change(x << 1, l, r, k); if (r > mid) change(x << 1 | 1, l, r, k); T[x].sum = T[x << 1].sum + T[x << 1 | 1].sum; return 0; } int get(int x, int l, int r) { int ans = 0; if (T[x].l >= l && T[x].r <= r) return T[x].sum; pushdown(x); int mid = (T[x].l + T[x].r) >> 1; if (l <= mid) ans += get(x << 1, l, r); if (r > mid) ans += get(x << 1 | 1, l, r); return ans; } void dealsum(int x, int y) { int ans = 0; while (node[x].tp != node[y].tp) { int fx = node[x].tp, fy = node[y].tp; if (node[fx].deep < node[fy].deep) swap(fx, fy), swap(x, y); ans += get(1, node[fx].dfn, node[x].dfn); x = node[fx].fa; } if (node[x].dfn > node[y].dfn) ans += get(1, node[y].dfn, node[x].dfn); else ans += get(1, node[x].dfn, node[y].dfn); cout << ans << endl; } signed main() { int Q; cin >> n >> Q; root = 1; int ls = -1; for (int i = 1; i <= n; i++) cin >> node[i].data; for (int i = 1; i <= n - 1; i++) { cin >> r[i].u >> r[i].v; r[i + n - 1] = r[i]; swap(r[i + n - 1].u, r[i + n - 1].v); } m = (n - 1) << 1; sort(r + 1, r + 1 + m, cmp); for (int i = 1; i <= m; i++) if (ls != r[i].u) ls = r[i].u, start[ls] = i; DFS1(root, 0); DFS2(root, root); build_tree(1, 1, n); for (int i = 1; i <= Q; i++) { int op, l, r, z; cin >> op; if (op == 1) { cin >> l >> z; change(1, node[l].dfn, node[l].dfn, z); } if (op == 2) { cin >> l >> z; change(1, node[l].dfn, node[l].rs, z); } if (op == 3) { cin >> l; dealsum(1, l); } } return 0; }