首先肯定是要先选好模板，并且把模板理解透彻
这个树链剖分的模板题 洛谷出的很好 https://www.luogu.org/problem/P3384
这个题目涉及了树链剖分的各种各样的操作
模板
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <stack>
#include <map>
#include <string>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 2e5 + 10;
int f[maxn];//f 保存u的父亲节点
int dep[maxn];//dep保存节点u 的深度
int siz[maxn];//siz保存以u为根的子节点的个数
int son[maxn];//son 保存u的重儿子
int rk[maxn];//rk当前dfs序在树中所对应的节点
int top[maxn];// top保存当前结点所在链的顶端结点
int id[maxn];//dfs的执行顺序
int a[maxn];
int mod, n;
int sum[maxn * 4], lazy[maxn * 4];
//------------------线段树部分---------------//
void push_up(int id)
{
sum[id] = (sum[id << 1] + sum[id << 1 | 1]) % mod;
// printf("sum[%d]=%d sum[%d]=%d
", id << 1, sum[id << 1], id << 1 | 1, sum[id << 1 | 1]);
// printf("sum[%d]=%d
", id, sum[id]);
}
void build(int id,int l,int r)
{
lazy[id] = 0;
if(l==r)
{
sum[id] = a[rk[l]] % mod;
// printf("id=%d sum=%d
", id, sum[id]);
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
push_up(id);
}
void push_down(int id,int len1,int len2)
{
if (lazy[id] == 0) return;
sum[id << 1] += lazy[id] % mod * len1%mod;
sum[id << 1] %= mod;
lazy[id << 1] += lazy[id] % mod;
lazy[id << 1] %= mod;
sum[id << 1 | 1] += lazy[id] % mod * len2%mod;
sum[id << 1 | 1] %= mod;
lazy[id << 1 | 1] += lazy[id] % mod;
lazy[id << 1 | 1] %= mod;
lazy[id] = 0;
}
void update(int id,int l,int r,int x,int y,int val)
{
// printf("id=%d l=%d r=%d x=%d y=%d val=%d
", id, l, r, x, y, val);
if(x<=l&&y>=r)
{
// printf("id=%d sum=%d
", id, sum[id]);
sum[id] += val * (r - l + 1) % mod;
sum[id] %= mod;
lazy[id] += val;
lazy[id] %= mod;
// printf("%d
", sum[id]);
return;
}
int mid = (l + r) >> 1;
push_down(id, mid - l + 1, r - mid);
if (x <= mid) update(id << 1, l, mid, x, y, val);
if (y > mid) update(id << 1 | 1, mid + 1, r, x, y, val);
push_up(id);
}
int query(int id,int l,int r,int x,int y)
{
if (x <= l && y >= r) return sum[id];
int mid = (l + r) >> 1, ans = 0;
push_down(id, mid - l + 1, r - mid);
if (x <= mid) ans = (ans + query(id << 1, l, mid, x, y)) % mod;
if (y > mid) ans = (ans + query(id << 1 | 1, mid + 1, r, x, y)) % mod;
return ans;
}
//------------------------树链剖分-------------------//
// int f[maxn];//f 保存u的父亲节点
// int dep[maxn];//dep保存节点u 的深度
// int siz[maxn];//siz保存以u为根的子节点的个数
// int son[maxn];//son 保存u的重儿子
// int rk[maxn];//rk当前dfs序在树中所对应的节点
// int top[maxn];// top保存当前结点所在链的顶端结点
// int id[maxn];//dfs的执行顺序
struct node
{
int v, nxt;
node(int v=0,int nxt=0):v(v),nxt(nxt){}
}ex[maxn];
int head[maxn], cnt = 0, tot;
void init()
{
cnt = 0, tot = 0;
memset(son, 0, sizeof(son));
memset(head, -1, sizeof(head));
}
void add(int u,int v)
{
ex[cnt] = node(v, head[u]);
head[u] = cnt++;
ex[cnt] = node(u, head[v]);
head[v] = cnt++;
}
void dfs1(int u,int fa,int depth)
{
f[u] = fa; dep[u] = depth; siz[u] = 1;
for(int i=head[u];i!=-1;i=ex[i].nxt)
{
int v = ex[i].v;
if (v == fa) continue;
dfs1(v, u, depth + 1);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
void dfs2(int u,int t)
{
top[u] = t;
id[u] = ++tot;//标记dfs序
rk[tot] = u;//序号tot对应的结点u
if (!son[u]) return;
dfs2(son[u], t);
/*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续，
一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/
for(int i=head[u];i!=-1;i=ex[i].nxt)
{
int v = ex[i].v;
if (v != son[u] && v != f[u]) dfs2(v, v);//一个点位于轻链底端，那么它的top必然是它本身
}
}
void update2(int x,int y,int z)//修改x到y路径的值
{
while(top[x]!=top[y])//不在同一条链上
{
if (dep[top[x]] < dep[top[y]]) swap(x, y);//x为深度大的链
update(1, 1, n, id[top[x]], id[x], z);//x为深度大的链
x = f[top[x]];//深度大的向上跳
}
if (dep[x] > dep[y]) swap(x, y); //这里x和y在同一条链
update(1, 1, n, id[x], id[y], z); //x和y这条链的更新
}
int query2(int x,int y)
{
int ret = 0;
while(top[x]!=top[y])
{
if (dep[top[x]] < dep[top[y]]) swap(x, y);
ret = (ret + query(1, 1, n, id[top[x]], id[x])) % mod;
x = f[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
ret = (ret + query(1, 1, n, id[x], id[y])) % mod;
return ret;
}
//------------------树链剖分结束-------------------//
int main()
{
init();
int m, r;
scanf("%d%d%d%d", &n, &m, &r, &mod);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i] %= mod;
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
}
dfs1(r, 0, 1), dfs2(r, r);
build(1, 1, n);
while(m--)
{
int opt, x, y, z;
scanf("%d", &opt);
if(opt==1)
{
scanf("%d%d%d", &x, &y, &z);
update2(x,y,z);
}
if(opt==2)
{
scanf("%d%d", &x, &y);
int ans = query2(x,y);
printf("%d
", ans);
}
if(opt==3)
{
scanf("%d%d", &x, &z);
update(1, 1, n, id[x], id[x] + siz[x] - 1, z);
}
if(opt==4)
{
scanf("%d", &x);
int ans = query(1, 1, n, id[x], id[x] + siz[x] - 1);
printf("%d
", ans);
}
}
}
然后就是一个简单的树链剖分的练习
树链剖分注意初始化和数组稍微要开大一点，不然容易re
https://vjudge.net/problem/CodeForces-343D
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <stack>
#include <map>
#include <string>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 5e5 + 10;
int f[maxn], dep[maxn], siz[maxn], son[maxn], rk[maxn], top[maxn], id[maxn];
int head[maxn], cnt, tot, sum[maxn * 4], lazy[maxn * 4], n;
struct node
{
int v, nxt;
node(int v=0,int nxt=0):v(v),nxt(nxt){}
}ex[maxn*4];
void init()
{
memset(son, 0, sizeof(son));
memset(head, -1, sizeof(head));
cnt = tot = 0;
}
void push_up(int id)
{
sum[id] = sum[id << 1] + sum[id << 1 | 1];
}
void build(int id,int l,int r)
{
lazy[id] = -1,sum[id] = 0;
if (l == r) return;
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
push_up(id);
}
void push_down(int id,int len1,int len2)
{
if (lazy[id] == -1) return;
sum[id << 1] = len1 * lazy[id];
sum[id << 1 | 1] = len2 * lazy[id];
lazy[id << 1] = lazy[id << 1 | 1] = lazy[id];
lazy[id] = -1;
}
void update(int id,int l,int r,int x,int y,int val)
{
if(x<=l&&y>=r)
{
sum[id] = val * (r - l + 1);
lazy[id] = val;
return;
}
int mid = (l + r) >> 1;
push_down(id, mid - l + 1, r - mid);
if (x <= mid) update(id << 1, l, mid, x, y, val);
if (y > mid) update(id << 1 | 1, mid + 1, r, x, y, val);
push_up(id);
}
int query(int id,int l,int r,int pos)
{
if (l == r) return sum[id];
int mid = (l + r) >> 1;
int ans = 0;
push_down(id, mid - l + 1, r - mid);
if (pos <= mid) ans += query(id << 1, l, mid, pos);
else ans += query(id << 1 | 1, mid + 1, r, pos);
return ans;
}
void add(int u,int v)
{
ex[cnt] = node(v, head[u]);
head[u] = cnt++;
ex[cnt] = node(u, head[v]);
head[v] = cnt++;
}
void dfs1(int u,int fa,int depth)
{
f[u] = fa, dep[u] = depth, siz[u] = 1;
for(int i=head[u];i!=-1;i=ex[i].nxt)
{
int v = ex[i].v;
if (v == fa) continue;
dfs1(v, u, depth + 1);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
void dfs2(int u,int t)
{
top[u] = t;//标记这个结点的顶端
id[u] = ++tot;//标记这个结点的标号
rk[tot] = u;//标号对应的结点
if (!son[u]) return;
dfs2(son[u], t);
for(int i=head[u];i!=-1;i=ex[i].nxt)
{
int v = ex[i].v;
if (v == u) continue;
if (v != son[u] && v != f[u]) dfs2(v, v);
}
}
void update1(int x,int y,int z)
{
while(top[x]!=top[y])
{
if (dep[top[x]] < dep[top[y]]) swap(x, y);
update(1, 1, n, id[top[x]], id[x], z);
x = f[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
update(1, 1, n, id[x], id[y], z);
}
int main()
{
init();
int m;
scanf("%d", &n);
for(int i=1;i<n;i++)
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
}
dfs1(1, 0, 1), dfs2(1, 1);
build(1, 1, n);
scanf("%d", &m);
while(m--)
{
int opt, v;
scanf("%d%d", &opt, &v);
if (opt == 1) update(1, 1, n, id[v], id[v] + siz[v] - 1, 1);
if (opt == 2) update1(v, 1, 0);
if (opt == 3) printf("%d
", query(1, 1, n, id[v]));
}
return 0;
}
然后就是学校oj的一个也很裸的树链剖分
https://10.64.70.166/problem/1005
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <stack>
#include <map>
#include <string>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int f[maxn], dep[maxn], siz[maxn], son[maxn], rk[maxn], top[maxn], ver[maxn];
int head[maxn], cnt, tot, n, a[maxn], m;
ll sum[maxn * 4], lazy[maxn * 4];
struct node
{
int v, nxt;
node(int v=0,int nxt=0):v(v),nxt(nxt){}
}ex[maxn*4];
void init()
{
memset(son, 0, sizeof(son));
memset(head, -1, sizeof(head));
cnt = tot = 0;
}
void push_up(int id)
{
sum[id] = sum[id << 1] + sum[id << 1 | 1];
}
void build(int id,int l,int r)
{
lazy[id] = 0;
if (l == r) {
sum[id] = a[rk[l]];
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
push_up(id);
}
void push_down(int id,int len1,int len2)
{
if (lazy[id] == 0) return;
sum[id << 1] += len1 * lazy[id];
sum[id << 1 | 1] += len2 * lazy[id];
lazy[id << 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
lazy[id] = 0;
}
void update(int id,int l,int r,int x,int y,int val)
{
if(x<=l&&y>=r)
{
sum[id] += val * (r - l + 1);
lazy[id] += val;
return;
}
int mid = (l + r) >> 1;
push_down(id, mid - l + 1, r - mid);
if (x <= mid) update(id << 1, l, mid, x, y, val);
if (y > mid) update(id << 1 | 1, mid + 1, r, x, y, val);
push_up(id);
}
ll query(int id,int l,int r,int pos)
{
if (l == r) return sum[id];
int mid = (l + r) >> 1;
ll ans = 0;
push_down(id, mid - l + 1, r - mid);
if (pos <= mid) ans += query(id << 1, l, mid, pos);
else ans += query(id << 1 | 1, mid + 1, r, pos);
return ans;
}
void add(int u,int v)
{
ex[cnt] = node(v, head[u]);
head[u] = cnt++;
ex[cnt] = node(u, head[v]);
head[v] = cnt++;
}
void dfs1(int u,int fa,int depth)
{
f[u] = fa, dep[u] = depth, siz[u] = 1;
for(int i=head[u];i!=-1;i=ex[i].nxt)
{
int v = ex[i].v;
if (v == fa) continue;
dfs1(v, u, depth + 1);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
void dfs2(int u,int t)
{
top[u] = t;//标记这个结点的顶端
ver[u] = ++tot;//标记这个结点的标号
rk[tot] = u;//标号对应的结点
if (!son[u]) return;
dfs2(son[u], t);
for(int i=head[u];i!=-1;i=ex[i].nxt)
{
int v = ex[i].v;
if (v == u) continue;
if (v != son[u] && v != f[u]) dfs2(v, v);
}
}
void update1(int x,int y,int z)
{
while(top[x]!=top[y])
{
if (dep[top[x]] < dep[top[y]]) swap(x, y);
update(1, 1, n, ver[top[x]], ver[x], z);
x = f[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
update(1, 1, n, ver[x], ver[y], z);
}
int opt[maxn], ux[maxn], vx[maxn], xx[maxn];
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i=1;i<n;i++)
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
}
dfs1(1, 0, 1), dfs2(1, 1);
build(1, 1, n);
for(int i=1;i<=m;i++)
{
scanf("%d", &opt[i]);
if(opt[i]==1)
{
scanf("%d%d", &ux[i], &xx[i]);
update(1, 1, n, ver[ux[i]], ver[ux[i]] + siz[ux[i]] - 1, xx[i]);
}
if(opt[i]==2)
{
scanf("%d%d%d", &ux[i], &vx[i], &xx[i]);
update1(ux[i], vx[i], xx[i]);
}
if(opt[i]==3)
{
int t;
scanf("%d", &t);
if(opt[t]==1)
{
ux[i] = ux[t], xx[i] = -xx[t];
update(1, 1, n, ver[ux[i]], ver[ux[i]] + siz[ux[i]] - 1, xx[i]);
}
if(opt[t]==2)
{
ux[i] = ux[t], vx[i] = vx[t], xx[i] = -xx[t];
update1(ux[i], vx[i], xx[i]);
}
}
if(opt[i]==4)
{
scanf("%d", &ux[i]);
ll ans = query(1, 1, n, ver[ux[i]]);
printf("%lld
", ans);
}
}
}
}