学习笔记——树链剖分

思想

对于每个节点，把所有子节点中子树最大的一个，成为重点，其它成为轻点。重点到父亲节点的连线成为重边，重边连接成若干条重链，其余的每个点称为重链。

可以发现，如果路径经过一条轻边，那么现在的子树大小至少缩小一半，所以每条路径可以被拆分成最多 \(\log n\) 条链，这样一来，就可以把较难维护的树形结构，改变成若干条链，并且可以发现按照先重后轻的原则遍历时，属于相同重链或相同子树的遍历序是连续的，就可以根据这个性质用线段树维护。

每个链在线段树上的区间是 \([dfn(top(u)),dfn(u)]\)，每个子树在线段树上的区间是 \([dfn(u),dfn(u)+siz(u)-1]\)，根据这个进行线段树操作。

模板

P3384 轻重链剖分/树链剖分

Code

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define re register
typedef int ll;
typedef double db;
typedef unsigned long long ull;
const int maxn=1e6+10;
const int maxm=1e6+10;
const ll mod=1e9+7;
const ull base1=19260817;
const ull base2=19660813;
const ll maxxn=0x7ffffff;
const ll minxn=-0x7ffffff;
const db inf=1e13;
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define len (r-l+1)
inline ll read(){
    ll x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}
inline void write(ll x){
    if(x<0){putchar('-');write(-x);return;}
    if(x>=10) write(x/10);
    putchar(x%10+'0');
}
ll n,m,root,p;
struct edge{
    ll to,nxt;
}e[maxn];
ll cnt,head[maxn];
ll w[maxn],dfnw[maxn];
ll fa[maxn],son[maxn],dep[maxn],siz[maxn];
ll dfn[maxn],top[maxn],dfncnt;
inline void add_edge(ll u,ll v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
//第一次dfs遍历深度，父亲，子树大小和重儿子
inline void dfs1(ll u,ll f,ll d){
    dep[u]=d,fa[u]=f,siz[u]=1;
    ll maxson=-1;
    for(int i=head[u];i;i=e[i].nxt){
        ll v=e[i].to;
        if(v==f) continue;
        dfs1(v,u,d+1);
        siz[u]+=siz[v];
        if(siz[v]>maxson){
            son[u]=v;
            maxson=siz[v];
        }
    }
}
//第二次dfs遍历重链的顶点和dfs序
inline void dfs2(ll u,ll t){
    dfn[u]=++dfncnt,dfnw[dfncnt]=w[u],top[u]=t;
    if(!son[u]) return;
    dfs2(son[u],t);//先遍历重儿子保证dfs序连续
    for(int i=head[u];i;i=e[i].nxt){
        ll v=e[i].to;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);//轻儿子是所在重链的顶点
    }
}
ll num[maxn],laz[maxn];
//线段树维护
struct XDS{
    inline void build(ll rt,ll l,ll r){
        if(l==r){
            num[rt]=dfnw[l]%p;
            return;
        }
        build(lson),build(rson);
        num[rt]=(num[rt<<1]+num[rt<<1|1])%p;
    }
    inline void push_down(ll rt,ll l,ll r){
        laz[rt<<1]+=laz[rt],laz[rt<<1|1]+=laz[rt];
        num[rt<<1]+=laz[rt]*(mid-l+1),num[rt<<1|1]+=laz[rt]*(r-mid);
        num[rt<<1]%=p,num[rt<<1|1]%=p,laz[rt]=0;
    }
    inline void update(ll rt,ll l,ll r,ll pl,ll pr,ll k){
        if(pl<=l&&r<=pr){
            laz[rt]+=k;
            num[rt]+=k*len;
        }
        else{
            if(laz[rt]) push_down(rt,l,r);
            if(pl<=mid) update(lson,pl,pr,k);
            if(pr>mid) update(rson,pl,pr,k);
            num[rt]=(num[rt<<1]+num[rt<<1|1])%p;
        }
    }
    inline ll query(ll rt,ll l,ll r,ll pl,ll pr){
        if(pl<=l&&r<=pr){
            return num[rt]%p;
        }
        else{
            if(laz[rt]) push_down(rt,l,r);
            ll sum=0;
            if(pl<=mid) sum+=query(lson,pl,pr);
            if(pr>mid) sum+=query(rson,pl,pr);
            return sum;
        }
    }
}tree;
//处理区间时，因为一定在一条重链向下延伸的重链中，所以一直向上跳深度较大的一点直到lca
inline void update_pt(ll x,ll y,ll k){
    k%=p;
    while(top[x]!=top[y]){
        if(dep[top[x]]dep[y]) swap(x,y);
    tree.update(1,1,n,dfn[x],dfn[y],k);
}
inline ll query_pt(ll x,ll y){
    ll sum=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]dep[y]) swap(x,y);
    sum=(sum+tree.query(1,1,n,dfn[x],dfn[y]))%p;
    return sum%p;
}
//处理子树时，因为dfs序一定是连续的，所以与线段树区间处理相同
inline void update_tr(ll x,ll k){
    tree.update(1,1,n,dfn[x],dfn[x]+siz[x]-1,k);
}
inline ll query_tr(ll x){
    return tree.query(1,1,n,dfn[x],dfn[x]+siz[x]-1)%p;
}
int main(){
    n=read(),m=read(),root=read(),p=read();
    for(int i=1;i<=n;i++){
        w[i]=read();
    }
    for(int i=1;i

例题

1.P2690 ZJOI2008 书的统计

甚至比模板还要简单，没有复杂的转换，只需要维护区间和以及区间最大值，直接树剖套线段树。

代码鸽了。

2.P2486 SDOI2011 染色

一道很有趣的题。

因为要维护连续颜色段数，线段树的查询和修改就略有不同，函数参数应为：当前下标，当前区间，当前查询区间，要求查询区间，这样能够维护出边界的颜色，来特判左右两段是否合并为一个。

ACcode

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define re register
typedef int ll;
typedef double db;
typedef unsigned long long ull;
const int maxn=1e6+10;
const int maxm=1e6+10;
const ll mod=1e9+7;
const ull base1=19260817;
const ull base2=19660813;
const ll maxxn=0x7ffffff;
const ll minxn=-0x7ffffff;
const db inf=1e13;
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define len (r-l+1)
inline ll read(){
    ll x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}
inline void write(ll x){
    if(x<0){putchar('-');write(-x);return;}
    if(x>=10) write(x/10);
    putchar(x%10+'0');
}
ll n,m;
struct edge{
    ll to,nxt;
}e[maxn];
ll cnt,head[maxn];
inline void add_edge(ll u,ll v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
ll w[maxn];
ll fa[maxn],son[maxn],dep[maxn],siz[maxn];
ll dfn[maxn],top[maxn],dfncnt;
inline void dfs1(ll u,ll f,ll d){
    dep[u]=d,fa[u]=f,siz[u]=1;
    ll maxson=-1;
    for(int i=head[u];i;i=e[i].nxt){
        ll v=e[i].to;
        if(v==f) continue;
        dfs1(v,u,d+1);
        siz[u]+=siz[v];
        if(siz[v]>maxson){
            son[u]=v;
            maxson=siz[v];
        }
    }
}
inline void dfs2(ll u,ll t){
    dfn[u]=++dfncnt,top[u]=t;
    if(!son[u]) return;
    dfs2(son[u],t);
    for(int i=head[u];i;i=e[i].nxt){
        ll v=e[i].to;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
ll num[maxn],laz[maxn],lc[maxn],rc[maxn];
ll cl,cr;
struct XDS{
	inline void push_down(ll rt){
		if(laz[rt]){
			laz[rt<<1]=laz[rt<<1|1]=laz[rt];
			num[rt<<1]=num[rt<<1|1]=1;
			lc[rt<<1]=rc[rt<<1]=lc[rt];
			lc[rt<<1|1]=rc[rt<<1|1]=lc[rt];
			laz[rt]=0;
		}
	}
	inline void push_up(ll rt){
		lc[rt]=lc[rt<<1],rc[rt]=rc[rt<<1|1];
		ll ans=num[rt<<1]+num[rt<<1|1];
		if(rc[rt<<1]==lc[rt<<1|1]) ans--;
		num[rt]=ans;
	}
	inline void build(ll rt,ll l,ll r){
		num[rt]=0;
		if(l==r){
			return;
		}
		build(lson),build(rson);
	}
	inline void update(ll rt,ll l,ll r,ll nl,ll nr,ll k){
		if(nl==l&&r==nr){
			num[rt]=laz[rt]=1;
			lc[rt]=rc[rt]=k;
			return;
		}
		push_down(rt);
		if(nr<=mid) update(lson,nl,nr,k);
		else if(nl>mid) update(rson,nl,nr,k);
		else{
			update(lson,nl,mid,k),update(rson,mid+1,nr,k);
		}
		push_up(rt);
	}
	inline ll query(ll rt,ll l,ll r,ll nl,ll nr,ll pl,ll pr){
		if(l==pl) cl=lc[rt];
		if(r==pr) cr=rc[rt];
		if(nl==l&&r==nr){
			return num[rt];
		}
		push_down(rt);
		if(pr<=mid) return query(lson,nl,nr,pl,pr);
		else if(pl>mid) return query(rson,nl,nr,pl,pr);
		else{
			ll ans=query(lson,nl,mid,pl,pr)+query(rson,mid+1,nr,pl,pr);
			if(rc[rt<<1]==lc[rt<<1|1]) ans--;
			return ans;
		}
		push_up(rt);
	}
}tree;
inline void update_pt(ll u,ll v,ll k){
	while(top[u]!=top[v]){
		if(dep[top[u]]dep[v]) swap(u,v);
	tree.update(1,1,n,dfn[u],dfn[v],k);
}
inline ll query_pt(ll u,ll v){
	ll ansl=-1,ansr=-1;
	ll ans=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]>opt;
		if(opt=='C'){
			ll u=read(),v=read(),k=read();
			update_pt(u,v,k);
		}
		else{
			ll u=read(),v=read();
			printf("%d\n",query_pt(u,v));
		}
	}
}

3.P2590 ZJOI2008 树的统计

模板题，代码不贴了。

4.P1967 货车运输

\(\operatorname{Kruskal}\)最大生成树重构一下，可以放到树剖里跑，因为维护的是树上边权最小值，可以把边权挂在子节点上，处理在同一重链的 \([L,R]\) 的路径时，线段树查询 \([L+1,R]\) 的最小值即可。

两个\(\operatorname{dfs}\)

ll fa[maxn],son[maxn],dep[maxn],siz[maxn];
ll dfn[maxn],top[maxn],tow[maxn],dfnw[maxn],dfncnt;
inline void dfs1(ll u,ll f,ll d){
	dep[u]=d,fa[u]=f,siz[u]=1;
	ll maxson=-1;
	for(int i=head[u];i;i=e[i].nxt){
		ll v=e[i].to;
		if(v==f) continue;
		tow[v]=e[i].w;
		dfs1(v,u,d+1);
		siz[u]+=siz[v];
		if(siz[v]>maxson){
			son[u]=v;
			maxson=siz[v];
		}
	}
}
inline void dfs2(ll u,ll t){
	dfn[u]=++dfncnt,dfnw[dfncnt]=tow[u],top[u]=t;
	if(!son[u]) return;
	dfs2(son[u],t);
	for(int i=head[u];i;i=e[i].nxt){
		ll v=e[i].to;
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}

查询操作

inline ll query_ptmin(ll u,ll v){
	ll ans=maxxn;
	while(top[u]!=top[v]){
		if(dep[top[u]]

5.P3979 遥远的国度

换根的树剖，支持区间修改和区间维护最小值。

对于换根，因为树的性质不变，所以如果在初始化以 \(1\) 为根的树中，现在根节点和查询节点同属一颗子树的同左或同右的子树，就直接查询这个子树，如果在异侧那就找到子树的根，然后查询两次。

ACcode

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define re register
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int maxn=1e5+10;
const int maxm=4e5+10;
const ll mod=1e9+7;
const ull base1=19260817;
const ull base2=19660813;
const ll maxxn=0x7fffffff;
const ll minxn=-0x7fffffff;
const db inf=1e13;
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define len (r-l+1)
inline ll read(){
    ll x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}
inline void write(ll x){
    if(x<0){putchar('-');write(-x);return;}
    if(x>=10) write(x/10);
    putchar(x%10+'0');
}
ll n,m,root;
struct edge{
	ll to,nxt;
}e[maxm];
ll head[maxn],cnt;
inline void add_edge(ll u,ll v){
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
ll w[maxn];
ll fa[maxn],son[maxn],dep[maxn],siz[maxn];
ll dfn[maxn],top[maxn],dfncnt,dfnw[maxn];
inline void dfs1(ll u,ll f,ll d){
	fa[u]=f,dep[u]=d,siz[u]=1;
	ll maxson=-1;
	for(int i=head[u];i;i=e[i].nxt){
		ll v=e[i].to;
		if(v==f) continue;
		dfs1(v,u,d+1);
		siz[u]+=siz[v];
		if(siz[v]>maxson){
			maxson=siz[v];
			son[u]=v;
		}
	}
}
inline void dfs2(ll u,ll t){
	dfn[u]=++dfncnt,dfnw[dfncnt]=w[u],top[u]=t;
	if(!son[u]) return;
	dfs2(son[u],t);
	for(int i=head[u];i;i=e[i].nxt){
		ll v=e[i].to;
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}	
}
ll minx[maxm],laz[maxm];
struct XDS{
	inline void push_up(ll rt){
		minx[rt]=min(minx[rt<<1],minx[rt<<1|1]);
	}
	inline void build(ll rt,ll l,ll r){
		if(l==r){
			minx[rt]=dfnw[l];
			return;
		}
		build(lson),build(rson);
		push_up(rt);
	}
	inline void push_down(ll rt){
		if(laz[rt]){
			laz[rt<<1]=laz[rt<<1|1]=laz[rt];
			minx[rt<<1]=minx[rt<<1|1]=laz[rt];
			laz[rt]=0;
		}
	}
	inline void updatex(ll rt,ll l,ll r,ll ql,ll qr,ll k){
		if(ql<=l&&r<=qr){
			minx[rt]=laz[rt]=k;
			return;
		}
		push_down(rt);
		if(ql<=mid) updatex(lson,ql,qr,k);
		if(qr>mid) updatex(rson,ql,qr,k);
		push_up(rt);
	}
	inline ll queryx(ll rt,ll l,ll r,ll ql,ll qr){
		if(ql<=l&&r<=qr){
			return minx[rt];
		}
		ll ans=maxxn;
		push_down(rt);
		if(ql<=mid) ans=min(ans,queryx(lson,ql,qr));
		if(qr>mid) ans=min(ans,queryx(rson,ql,qr));
		push_up(rt);
		return ans;
	}
}tree;
inline void update_pt(ll u,ll v,ll k){
	while(top[u]!=top[v]){
		if(dep[top[u]]dep[v]) swap(u,v);
	tree.updatex(1,1,n,dfn[u],dfn[v],k);
}
inline ll find(ll u){
	if(u==root) return -1;
	if(dfn[u]>=dfn[root]||dfn[u]+siz[u]-1

5.P1505 国家集训队 旅游

多用懒标记维护几个东西就ok了，因为要维护最大值以及最小值，所以取负的时候直接交换最大最小值。

放个上传和下传代码

inline void push_up(ll rt){
	maxx[rt]=max(maxx[rt<<1],maxx[rt<<1|1]);
	minx[rt]=min(minx[rt<<1],minx[rt<<1|1]);
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
inline void push_down(ll rt){
	laz[rt<<1]^=1,laz[rt<<1|1]^=1;
	maxx[rt<<1]=-maxx[rt<<1],maxx[rt<<1|1]=-maxx[rt<<1|1];
	minx[rt<<1]=-minx[rt<<1],minx[rt<<1|1]=-minx[rt<<1|1];
	sum[rt<<1]=-sum[rt<<1],sum[rt<<1|1]=-sum[rt<<1|1];
	swap(maxx[rt<<1],minx[rt<<1]);
	swap(maxx[rt<<1|1],minx[rt<<1|1]);
	laz[rt]=0;
}

6.P3258 JLOI2014 松鼠的新家

区间修改+单点查询

注意每次走的终点要减\(1\)，因为会重复。

7.P2146 NOI2015 软件包管理器

  • 安装操作：把根节点到当前节点路径赋值为\(1\)
  • 卸载操作：当前节点子树赋值为\(0\)

输出变化量。

学习笔记

相关

Git--学习笔记（三）远程仓库克隆到本地

[学习笔记] 整数规划之割平面法 How and why?

计网学习笔记(5) - 物理层与媒介

selenium python学习笔记之八 窗口截图、验证码处理

AntDesign vue学习笔记（三）嵌套路由使用

vue学习笔记（一）--来源尚硅谷

【学习笔记】TSlib校准原理

Go语言核心36讲（Go语言实战与应用六）--学习笔记

docker 学习笔记-7

SpringMVC学习笔记

Spring 学习笔记

[机器学习笔记(一)] TensorFLow安装

标签

一品网 冀ICP备14022925号-6