「树链剖分 - 学习笔记」

树链剖分似乎是个很强大的东西

可惜我之前不会啊

所以就mark一下啊

定义

树链剖分 简称树剖.对于一般的树上路径/权值的问题,Tarjan的LCA在线性内就可以快速求解.

如果要修改点权或者边权呢?

树链剖分就是用来解决动态修改树上权值并求解的问题的

一般树链剖分更新权值的复杂度为$O(logn)$,统计路径信息的复杂度为$O((logn)^2)$

内容

某些一定要知道的概念

• 重节点：子树结点数目最多的节点；
• 轻节点：父亲节点中除了重结点以外的节点；
• 重边：父亲节点和重节点连成的边；
• 轻边：父亲节点和轻节点连成的边；
• 重链：由多条重边连接而成的路径；
• 轻链：由多条轻边连接而成的路径；

这些东西有一个性质.

1.一条重链在线段树上是一段连续的区间。

2.一个节点的重儿子就是这个节点的子节点中子树最大的点。

所以第一次dfs求出重儿子

第二次通过dfs时间戳(dfn),得出节点新编号,并且将各个重节点连接成重链，轻节点连接成轻链

将重链（其实就是一段区间）用数据结构（一般是树状数组或线段树）来进行维护

为每个节点进行编号，其实就是DFS在执行时的顺序（id数组）

以及当前节点所在链的起点（top数组），还有当前节点在树中的位置（rnk数组）.

//dfs1
void dfs1(int u, int F, int depth) {
    dep[u] = depth;
    fa[u] = F;
    siz[u] = 1;
    for (int i = head[u]; i; i = E[i].next) {
        int v = E[i].to;
        if (v != fa[u]) { //如果不是父节点就继续向下找节点
            dfs1(v, u, depth + 1);
            siz[u] += siz[v];//加子结点的sz
            if ((!hson[u]) || siz[v] > siz[hson[u]]) hson[u] = v;//如果没有重孩子或者此孩子的sz较大则更新hson[u]
        }
    }
}

//dfs2
void dfs2(int u, int t) {
    dfn[u] = ++dfs_cnt; rnk[dfs_cnt] = u; top[u] = t;//维护u顶点的节点t
    if (!hson[u]) return ;//不是重儿子就return
    dfs2(hson[u], t);//继续向下找重链
    for (int i = head[u]; i; i = E[i].next) {
        int v = E[i].to;
        if (v != hson[u] && v != fa[u]) dfs2(v, v);//找其他非u为顶点的链
    }
}

LUOGU P3384 树链剖分[模板]

//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define PER(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
#define lc o<<1
#define rc o<<1|1
using namespace std;
inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}
const int MAXN = 110000;
struct Node {
    int to, next;
} E[MAXN<<1];
struct segmentTree {
    int L, R;
    int sum, tag;
} tree[MAXN<<2];
int head[MAXN], siz[MAXN], top[MAXN], hson[MAXN];
int dep[MAXN], fa[MAXN], dfn[MAXN], rnk[MAXN];
int N, M, R, A[MAXN], cnt = 0, dfs_cnt = 0,mod;
inline void adde(int u, int v) {
    E[++cnt].to = v; E[cnt].next = head[u]; head[u] = cnt;
}
void dfs1(int u, int F, int depth) {
    dep[u] = depth;
    fa[u] = F;
    siz[u] = 1;
    for (int i = head[u]; i; i = E[i].next) {
        int v = E[i].to;
        if (v != fa[u]) {
            dfs1(v, u, depth + 1);
            siz[u] += siz[v];
            if ((!hson[u]) || siz[v] > siz[hson[u]]) hson[u] = v;
        }
    }
}
void dfs2(int u, int t) {
    dfn[u] = ++dfs_cnt; rnk[dfs_cnt] = u; top[u] = t;
    if (!hson[u]) return ;
    dfs2(hson[u], t);
    for (int i = head[u]; i; i = E[i].next) {
        int v = E[i].to;
        if (v != hson[u] && v != fa[u]) dfs2(v, v);
    }
}
void Build(int o, int l, int r) {
    tree[o].L = l; tree[o].R = r;
    if (l == r) tree[o].sum = A[rnk[l]];
    else {
        int mid = (l + r) >> 1;
        Build(lc, l , mid);
        Build(rc | 1, mid + 1, r);
        tree[o].sum = tree[lc].sum + tree[rc].sum;
    }
}
void pushdown(int o) {
    tree[lc].sum += (tree[lc].R - tree[lc].L + 1) * tree[o].tag;
    tree[rc].sum += (tree[rc].R - tree[rc].L + 1) * tree[o].tag;
    tree[lc].tag += tree[o].tag;
    tree[rc].tag += tree[o].tag;
    tree[o].tag = 0;
}
void update(int o, int x, int y, int z) {
    if (tree[o].L > y || tree[o].R < x) return ;
    if (x <= tree[o].L && tree[o].R <= y) {
        tree[o].sum += (tree[o].R - tree[o].L + 1) * z;
        tree[o].tag += z;
    } else {
        if (tree[o].tag) pushdown(o);
        update(lc, x, y, z);
        update(rc, x, y, z);
        tree[o].sum = tree[lc].sum + tree[rc].sum;
    }
}
int query(int o, int x, int y) {
    if (x <= tree[o].L && tree[o].R <= y) return tree[o].sum;
    if (tree[o].L > y || tree[o].R < x) return 0;
    if (tree[o].tag) pushdown(o);
    return query(lc, x, y) + query(rc, x, y);
}
void update_path(int u, int v, int z) {
    int tu = top[u], tv = top[v];
    while (tu != tv) {
        if (dep[tu] < dep[tv]) swap(u, v), swap(tu, tv);
        update(1, dfn[tu], dfn[u], z);
        u = fa[tu], tu = top[u];
    }
    if (dep[u] < dep[v]) swap(u, v);
    update(1, dfn[v], dfn[u], z);
}
int query_path(int u, int v) {
    int res = 0;
    int tu = top[u], tv = top[v];
    while (tu != tv) {
        if (dep[tu] < dep[tv]) swap(u, v), swap(tu, tv);
        res += query(1, dfn[tu], dfn[u]);
        u = fa[tu], tu = top[u];
    }
    if (dep[u] < dep[v]) swap(u, v);
    return res + query(1, dfn[v], dfn[u]);
}
signed main(signed argc, char *argv[]) {
    N = read(), M = read(), R = read(), mod = read();
    REP(i, 1, N) A[i] = read();
    REP(i, 2, N) {
        int u = read(), v = read();
        adde(u, v); adde(v, u);
    }
    dfs1(R, 0, 1);
    dfs2(R, R);
    //REP(i,1,N) printf("%d %d %d %d %d\n",i,fa[i],dfn[i],siz[i],dep[i]);
    Build(1, 1, N);
    while (M--) {
        int opt = read();
        switch (opt) {
            case 1: {
                int x = read(), y = read();
                int z; scanf("%lld", &z);
                update_path(x, y, z);
                break;
            }
            case 2: {
                int x = read(), y = read();
                printf("%lld\n", query_path(x, y) % mod);
                break;
            }
            case 3: {
                int x = read();
                int z; scanf("%lld", &z);
                update(1, dfn[x], dfn[x] + siz[x] - 1, z);
                break;
            }
            case 4: {
                int x = read();
                printf("%lld\n", query(1, dfn[x], dfn[x] + siz[x] - 1) % mod);
            }
        }
    }
    return 0;
}

POJ-2763

基于边权修改的树剖.

//my vegetable has exploded. :(
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
// #define int long long
using namespace std;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}
const int MAXN = 1e5+10;
///------------------head------------------
#define lc o<<1
#define rc o<<1|1
int fa[MAXN],hson[MAXN],dep[MAXN],dfn[MAXN],rnk[MAXN],top[MAXN],sz[MAXN],val[MAXN];
int head[MAXN],cnt=0,dfs_cnt=0;
int n,m,s;
struct Edge{
	int u,v,val;
	inline void R(){
		u=read();v=read();val=read();
	}
	Edge(int uu=0,int vv=0,int vval=0):u(uu),v(vv),val(vval){}
}Edges[MAXN];
struct E{
  int to,next;
}E[MAXN<<1];
struct SegmentTree{
  int L,R,val;
}Tree[MAXN<<2];
inline void adde(int u, int v) {
    E[++cnt].to = v; E[cnt].next = head[u]; head[u] = cnt;
}
void dfs1(int u, int father, int depth) {
    dep[u] = depth;
    fa[u] = father;
    sz[u] = 1;
    for (int i = head[u]; i; i = E[i].next) {
        int v = E[i].to;
        if (v != fa[u]) {
            dfs1(v, u, dep[u]+1);
            sz[u] += sz[v];
            if (hson[u] == -1 || sz[v] > sz[hson[u]]) hson[u] = v;
        }
    }
}
void dfs2(int u, int t) {
    dfn[u] = ++dfs_cnt; rnk[dfs_cnt] = u; top[u] = t;
    if (!hson[u]) return ;
    dfs2(hson[u], t);
    for (int i = head[u]; i; i = E[i].next) {
        int v = E[i].to;
        if (v != hson[u] && v != fa[u]) dfs2(v, v);
    }
}
void pushup(int o){Tree[o].val = Tree[lc].val + Tree[rc].val;}
void build(int l,int r,int o){
	Tree[o].L = l;
	Tree[o].R = r;
	if (l == r) {Tree[o].val = val[l]; return;}
	int mid = (l + r) >> 1;
	build(l,mid,lc);
	build(mid+1,r,rc);
	pushup(o);
}
void Update(int o,int v,int val){
	if (Tree[o].L == Tree[o].R) {Tree[o].val = val; return ;}
	int mid = (Tree[o].L + Tree[o].R) >> 1;
	if (v <= mid) Update(lc,v,val);
		else Update(rc,v,val);
	pushup(o);
}
int query(int o,int l,int r){
	if(Tree[o].L >= l && Tree[o].R <= r) return Tree[o].val;
	int mid = (Tree[o].L + Tree[o].R) >> 1;
	if (r <= mid) return query(lc,l,r);
	else if (l > mid) return query(rc,l,r);
	else return query(lc,l,mid)+query(rc,mid+1,r);
}
int Query(int u,int v){
	int tp1 = top[u],tp2 = top[v];
	int ret = 0;
	while(tp1 != tp2){
		if (dep[tp1] < dep[tp2]) {
			swap(u,v); swap(tp1,tp2);
		}
		ret += query(1,dfn[tp1],dfn[u]);
		u = fa[tp1];
		tp1 = top[u];
	}
	if(u == v) return ret;
	if(dep[u] > dep[v]) swap(u,v);
	ret += query(1,dfn[hson[u]],dfn[v]);
	return ret;
}
signed main(signed argc, char *argv[]){
	n=read(),m=read(),s=read();
	rep(i,1,n-1){Edges[i].R();adde(Edges[i].u,Edges[i].v);adde(Edges[i].v,Edges[i].u);}
	dfs1(1,0,1);
	dfs2(1,1);
	rep(i,1,n-1){
		if (dep[Edges[i].u] < dep[Edges[i].v]) swap(Edges[i].u,Edges[i].v);
		val[dfn[Edges[i].u]] = Edges[i].val;
	}
	build(1,dfs_cnt,1);
	rep(i,1,m){
		int op=read(),x,y;
		if(!op){x=read();printf("%d\n",Query(s,x));s=x;}
		else{x=read(),y=read();Update(1,dfn[Edges[x].u],y);}
	}
	return 0;
}

/* Examples: */
/*in
3 3 1
1 2 1
2 3 2
0 2
1 2 3
0 3
*/

/*out
1
3
*/

:）karriganasta