首页 > 其他分享 > 树链剖分

树链剖分

时间：2023-11-10 17:55:36浏览次数：38  
标签：剖分 int hs dfs 树链 seg 重链 id

树链剖分

一、树链剖分的概念和写法

1.1概念

定义：树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。

树链剖分（树剖/链剖）有多种形式，如 重链剖分，长链剖分 和用于 Link/cut Tree 的剖分（有时被称作「实链剖分」），大多数情况下（没有特别说明时），「树链剖分」都指「重链剖分」。

树链剖分一般可以做：路径修改\查询，子树修改\查询

一些定义：

定义 重儿子节点 表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。

定义 轻儿子节点 表示剩余的所有子结点。

从这个结点到重子节点的边为 重边。

到其他轻子节点的边为 轻边。

若干条首尾衔接的重边构成 重链。

把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。

image

我们观察图中，重链是以轻儿子或整棵树的根为起点，依次向下连接所有重儿子组成的链。而轻链是以重链为主干链，其分支的链为轻链的，且向外扩展长度为1。

轻链的本质就是一些长度为1的边，将他们作为桥梁连接下一个重链。同时还可以看出，轻儿子(除去叶子结点)都是下一条重链的起始结点。

两遍dfs就是树链剖分的主要处理，通过dfs我们已经保证一条重链上各个节点dfs序连续，那么可以想到，我们可以通过数据结构（以线段树为例）来维护一条重链的信息

第一遍\(dfs\)处理每个点的重儿子\(hs\),节点大小\(sz\)，深度\(dep\),每个点的父亲\(f\)

第二遍\(dfs\)，求出每个点的\(dfs\)序，重链上的链头的元素\(top\)。

❗关于第二遍\(dfs\)：

首先根据\(hs\)，先\(dfs\)所有的重链，遍历重链过程中，传递下去\(top\)值；再以重链为主干，遍历所有的轻链，因为轻结点会是重链的起点，因此，又可以得到新的重链，依次下去。同时先\(dfs\)重链，保证了重链的\(dfs\)序的连续的,即不仅在子树里面dfs序是连续的，在重链里面也是连续的。

HLD

为什么要记录链头元素？(该部分引用自)

我们得到了一系列的重链，如何对它们快速操作？那么就是记录链头元素。这样我们就可以直接跳到链头元素。但是我们遇到了一个问题：在同一条重链上可以直接跳到头部，如果不是在同一条链上呢？方法是：从这条重链的头部再往上跳，到他的父亲结点，必定在另外一条重链上，然后根据需求继续跳。如图所示，b结点跳跃的过程：

b节点跳跃示意图

b在{6 b}这条重链，跳至6号结点，从6号再跳到{1 2 4 5 a}这条重链，再跳就是1根节点。到这里，再想想什么是轻链，理解会更深刻“将他们作为“桥梁”连接下一个重链”。

1.2 (重要)性质

经过轻边，子树大小翻倍。一个点往上走，最多走\(O(\log n)\)条轻边。任意两点u，v，最多经过\(O(\log n)\)条。重链也是不超过\(O(\log n)\)段的。

1.3基本实现

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
vector<int>e[N];
int l[N],r[N],id[N],sz[N],hs[N],tot,dep[N],f[N],top[N];
//第一遍dfs处理每个点的重儿子,节点大小，深度,每个点的父亲
void dfs1(int u,int fa)
{
	sz[u] = 1;
	hs[u] = -1;
	dep[u] = dep[fa]+1;
	f[u] = fa
	for(auto v:e[u])
	{
		if(v==fa)continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(hs[u]==-1||sz[v]>sz[hs[u]])hs[u] = v;
	}
}

//第二步dfs，求出每个点的dfs序，重链上的链头的元素
void dfs2(int u,int t)//keep表示需不需要保留当前信息
{
	top[u] = t;
	l[u] = ++tot;
	id[tot] = u;

	if(hs[u]!=-1)
		dfs2(hs[u],t);//重儿子的集合
	for(auto v:e[u])
	{
		if(v!=fa[u]&&v!=hs[u])//v是轻儿子,它的链头就是它本身
		{
			dfs2(v,v);
		}
	}
	r[u] = tot;
}

int main()
{
	cin>>n;
	for(int i = 1;i<=n;i++)
	{
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(1,1);
	return 0;
}

1.4 简单应用：树链剖分求\(LCA\)

预处理时间复杂度\(O(n)\)，查询时间复杂度\(O(\log n)\)

在这里插入图片描述

以上图为例，求\(a,b\)的\(LCA\)。

首先思考两个问题：

  1. 谁先跳？

    深度大的先跳。这时候你会想，那\(a，b\)的深度一样呀。不是的，不是直接比较\(a，b\)的深度，而是比较\(a，b\)向上跳一个链的深度。\(b\)结点所在的重链往上跳一个链就是到\(4\)号结点，而\(a\)所在重链，往上跳也就是到\(1\)了。我们需要比较的是\(1\)号和\(4\)号结点的深度，显然\(4\)号深度更大，那么\(b\)先跳。

  2. 什么时候能判断出\(LCA\)？
    如果两个点在同一重链上，那么深度较小的，为\(LCA\)，否则还是要不断的跳。\(a、b\)结点，当\(b\)结点跳到\(4\)结点时，\(a\)和\(4\)在同一重链中，即\(top[a]==top[4]\)，所以\(4\)为\(a、b\)最终的\(LCA\)。

例题：树上LCA2 

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
vector<int>e[N];
int l[N],r[N],id[N],sz[N],hs[N],tot,dep[N],f[N],top[N];
int n,m;
//第一遍dfs处理每个点的重儿子,节点大小，深度,每个点的父亲
void dfs1(int u,int fa)
{
	sz[u] = 1;
	hs[u] = -1;
	dep[u] = dep[fa]+1;
	f[u] = fa;
	for(auto v:e[u])
	{
		if(v==fa)continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(hs[u]==-1||sz[v]>sz[hs[u]])hs[u] = v;
	}
}

//第二步dfs，求出每个点的dfs序，重链上的链头的元素
void dfs2(int u,int t)//keep表示需不需要保留当前信息
{
	
	l[u] = ++tot;
	id[tot] = u;
	top[u] = t;
	if(hs[u]!=-1)
		dfs2(hs[u],t);//重儿子的集合
	for(auto v:e[u])
	{
		if(v!=f[u]&&v!=hs[u])//v是轻儿子,它的链头就是它本身
		{
			dfs2(v,v);
		}
	}
	r[u] = tot;
}

int LCA(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])v = f[top[v]];
		else u = f[top[u]];
	}
	if(dep[u]<dep[v])return u;
	else return v;
}


int main()
{
	cin>>n;
	for(int i = 1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(1,1);
	cin>>m;
	for(int i = 1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		cout<<LCA(u,v)<<"\n";	
	}
	return 0;
}

二、树链剖分的路径查询

根据上面第一点中所说的，在第二遍\(dfs\)中，先\(dfs\)重链，再\(dfs\)轻链，这样保证了\(dfs\)序不仅在子树中是连续的，在重链中也是连续的。

此时我们考虑对整个\(dfs\)序建线段树。我们重链的一段，就是\(dfs\)序的一段。

考虑一个点\(v\)跳到\(f[top[v]]\)，我们需要维护的就是\(top[v]\)到\(v\)的信息，再让\(v = f[top[v]]\)。即每跳一段就维护一段的信息。即在\(dfs\)序中\(l[top[v]]\)到\(l[v]\)这一段（\(l[]\)就是\(dfs\)序的编号）

image

例题：SDOI2011, 染色

题意：

给定一棵\(n\)个节点的无根树，共有$ m$ 个操作，操作分为两种：

  1. 将节点 \(a\) 到节点 \(b\) 的路径上的所有点（包括 \(a\)和$ b$）都染成颜色 \(c\)。
  2. 询问节点 \(a\)到节点 \(b\)的路径上的颜色段数量。

颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成：11、222、1。

思路：考虑从\(a\)到\(b\)的路径，那要考虑要两边一起跳。

注意点如下图：

image
\(dfs\)序和我们实际路径可能是反着的，这个要注意！

image
注意拼接顺序❗\(ansu = ansu + query\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
vector<int>e[N];
int l[N],r[N],idx[N],sz[N],hs[N],tot,dep[N],f[N],top[N],w[N];
int n,m;
struct info
{
    int lc,rc,seg;
};

info operator+(const info &l,const info &r)
{
    return (info){l.lc,r.rc,l.seg+r.seg+(l.rc!=r.lc)};
}

struct node{
    info val;
    int t;
}seg[N*4];


void settag(int id,int t)
{
    seg[id].val = {t,t,0};
    seg[id].t = t;
}

void pushdown(int id)
{
    if(seg[id].t!=0)
    {
        settag(id*2,seg[id].t);
        settag(id*2+1,seg[id].t);
        seg[id].t = 0;
    }
}
void update(int id)
{
    seg[id].val = seg[id*2].val+seg[id*2+1].val;
}

void build(int id,int l,int r)
{
    if(l==r)
    {
        //l号点，dfs序中第l个点,而不是a[l],这里要注意❗
        //seg[id].val = {a[l],a[l]};
        seg[id].val = {w[idx[l]],w[idx[l]],0};
    }
    else 
    {
        int mid = (l+r)>>1;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
        update(id);
    }
}


void modify(int id,int l,int r,int x,int y,int t){
    if(l==x&&r==y)
    {
        settag(id,t);
        return;
    }
    int mid = (l+r)/2;
    pushdown(id);
    if(y<=mid) modify(id*2,l,mid,x,y,t);
    else if(x>mid) modify(id*2+1,mid+1,r,x,y,t);
    else{
        modify(id*2,l,mid,x,mid,t),modify(id*2+1,mid+1,r,mid+1,y,t);
    }
    update(id);
}

//O(logn)
info query(int id,int l,int r,int x,int y)
{
    if(l==x&&r==y)return seg[id].val; 
    int mid = (l+r)/2;
    pushdown(id);
    if(y<=mid)return query(id*2,l,mid,x,y);
    else if(x>mid)return query(id*2+1,mid+1,r,x,y);
    else{
        return query(id*2,l,mid,x,mid)+query(id*2+1,mid+1,r,mid+1,y);
    }

}

//第一遍dfs处理每个点的重儿子,节点大小，深度,每个点的父亲
void dfs1(int u,int fa)
{
    sz[u] = 1;
    hs[u] = -1;
    dep[u] = dep[fa]+1;
    f[u] = fa;
    for(auto v:e[u])
    {
        if(v==fa)continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(hs[u]==-1||sz[v]>sz[hs[u]])hs[u] = v;
    }
}

//第二步dfs，求出每个点的dfs序，重链上的链头的元素
void dfs2(int u,int t)//keep表示需不需要保留当前信息
{
    
    l[u] = ++tot;
    idx[tot] = u;
    top[u] = t;
    if(hs[u]!=-1)
        dfs2(hs[u],t);//重儿子的集合
    for(auto v:e[u])
    {
        if(v!=f[u]&&v!=hs[u])//v是轻儿子,它的链头就是它本身
        {
            dfs2(v,v);
        }
    }
    r[u] = tot;
}

int LCA(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])v = f[top[v]];
        else u = f[top[u]];
    }
    if(dep[u]<dep[v])return u;
    else return v;
}


int query(int u,int v)
{
    info ansu = {0,0,-1},ansv={0,0,-1};
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]]){
            ansv = query(1,1,n,l[top[v]],l[v]) + ansv;//在前面加一段
            v = f[top[v]];
        }
        else{
            ansu = query(1,1,n,l[top[u]],l[u]) + ansu;
            u = f[top[u]];
        }
    }
    if(dep[u]<=dep[v])ansv = query(1,1,n,l[u],l[v])+ansv;
    else ansu = query(1,1,n,l[v],l[u])+ansu;
    return ansu.seg+ansv.seg+(ansu.lc!=ansv.lc)+1;
}

void modify(int u,int v,int c)
{
    // while(top[u]!=top[v])
    // {
    //     if(dep[top[u]]<dep[top[v]]){
    //        modify(1,1,n,l[top[v]],l[v],c);
    //        v = f[top[v]];
    //     }
    //     else{
    //         modify(1,1,n,l[top[u]],l[u],c);
    //         u = f[top[u]];
    //     }
    // }
    // if(dep[u]<=dep[v])modify(1,1,n,l[u],l[v],c);
    // else modify(1,1,n,l[v],l[u],c);

    while(top[u]!=top[v])
    {
        if(dep[top[u]]>dep[top[v]])swap(u,v);
        modify(1,1,n,l[top[v]],l[v],c);
        v = f[top[v]];
    }
    if(dep[u]>dep[v])swap(u,v);
    modify(1,1,n,l[u],l[v],c);
}

int main()
{
    cin>>n>>m;
    for(int i = 1;i<=n;i++)
        cin>>w[i];
    for(int i = 1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }


    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    for(int i = 1;i<=m;i++)
    {
        char op;
        cin>>op;
        if(op=='Q')
        {
            int u,v;
            cin>>u>>v;
            cout<<query(u,v)<<endl;
        }
        else
        {
            int u,v,c;
            cin>>u>>v>>c;
            modify(u,v,c);
        }
    }
    return 0;
}

三、树链剖分的子树查询

例题：NOI2015, 软件包管理器

题意：要下载某一个软件，就要把该软件到根路径上的所有没下载的软件都下载了。问每次操作完，有多少个软件包状态发生改变(从安装到没安装，或者从没安装到安装)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
vector<int>e[N];
int l[N],r[N],idx[N],sz[N],hs[N],tot,dep[N],f[N],top[N],w[N];
int n,m;

struct node{
    int cnt;
    int sz;
    int t;
}seg[N*4];


void settag(int id,int t)
{
    if(t==1)
        seg[id].cnt = seg[id].sz;
    else seg[id].cnt = 0;
    seg[id].t = t;
}

void pushdown(int id)
{
    if(seg[id].t!=-1)
    {
        settag(id*2,seg[id].t);
        settag(id*2+1,seg[id].t);
        seg[id].t = -1;
    }
}
void update(int id)
{
    seg[id].cnt= seg[id*2].cnt+seg[id*2+1].cnt;
}

void build(int id,int l,int r)
{
    seg[id].sz = (r-l+1);
    seg[id].t = -1;
    if(l==r)
    {
        seg[id].cnt = 0;
    }
    else 
    {
        int mid = (l+r)>>1;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
        update(id);
    }
}


void modify(int id,int l,int r,int x,int y,int t){
    if(l==x&&r==y)
    {
        settag(id,t);
        return;
    }
    int mid = (l+r)/2;
    pushdown(id);
    if(y<=mid) modify(id*2,l,mid,x,y,t);
    else if(x>mid) modify(id*2+1,mid+1,r,x,y,t);
    else{
        modify(id*2,l,mid,x,mid,t),modify(id*2+1,mid+1,r,mid+1,y,t);
    }
    update(id);
}


//第一遍dfs处理每个点的重儿子,节点大小，深度,每个点的父亲
void dfs1(int u,int fa)
{
    sz[u] = 1;
    hs[u] = -1;
    dep[u] = dep[fa]+1;
    f[u] = fa;
    for(auto v:e[u])
    {
        if(v==fa)continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(hs[u]==-1||sz[v]>sz[hs[u]])hs[u] = v;
    }
}

//第二步dfs，求出每个点的dfs序，重链上的链头的元素
void dfs2(int u,int t)//keep表示需不需要保留当前信息
{
    
    l[u] = ++tot;
    idx[tot] = u;
    top[u] = t;
    if(hs[u]!=-1)
        dfs2(hs[u],t);//重儿子的集合
    for(auto v:e[u])
    {
        if(v!=f[u]&&v!=hs[u])//v是轻儿子,它的链头就是它本身
        {
            dfs2(v,v);
        }
    }
    r[u] = tot;
}

void install(int x)
{
    while(x!=0)
    {
        modify(1,1,n,l[top[x]],l[x],1);
        x = f[top[x]];
    }
}




void uninstall(int x)
{
    modify(1,1,n,l[x],r[x],0);
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i = 2;i<=n;i++)
    {
         cin>>f[i];
         ++f[i];
         e[f[i]].push_back(i);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    cin>>m;
    int pre = 0;
    for(int i = 1;i<=m;i++)
    {
        string op;
        int x;
        cin>>op>>x;
        x++;
        if(op=="install")
        {
            install(x);
        }
        else
        {
            uninstall(x);
        }
        cout<<abs(seg[1].cnt-pre)<<"\n";
        pre = seg[1].cnt;
    }
    return 0;
}

四、总结

树链剖分把路径问题转为为\(O(\log n)\)个区间问题。

标签：剖分,int,hs,dfs,树链,seg,重链,id
From： https://www.cnblogs.com/nannandbk/p/17824701.html

相关文章

  • 重链剖分
    前置芝士：线段树，或树状数组，越熟练越好。（当然这不是意味着你不会线段树就看不懂这篇博客。）1.何为树链剖分树链剖分，简而言之，就是将树分成一条条链，然后用数据结构去维护这些链，以支持树上两点间的各种询问操作。据我所知，树链剖分大约有三种，分别是重链剖分、长链剖分和实链剖分。其......
  • 点集合的三角剖分
    点集合的三角剖分是指如何将一些离散的点集合组合成不均匀的三角形网格，使得每个点成为三角网中三角面的顶点。这个算法的用处很多，一个典型的意义在于可以通过一堆离散点构建的TIN实现对整个构网区域的线性控制，比如用带高程的离散点构建的TIN来表达地形。在实际工作中，使用最多的三......
  • 树链剖分
    注意事项：线段树中\(modify(),query()\)中\(>=，<=,>,<\)以及\(l,r,L,R\)#include<bits/stdc++.h>#definelsp<<1#definersp<<1|1#definelsonls,l,mid#definersonrs,mid+1,r#defineroot1,1,nusingnamespacestd;constint......
  • 树链剖分 学习心得
    Bug都写在代码开头了，就不复述了。还有一个智障的错误是注释调试代码的时候把同一行的正式代码也给注释掉了（写得非常精彩。/*  bug:1.rev、id要分清！      2.mod()函数的情况不能写一半就跑路！      3.别忘了先给tree build()一下！      4.出界......
  • 重链剖分
    代码思路主体部分：初始化，剖分链，求LCA（也就是dfs1，dfs2，LCA三个函数）辅助部分：structPoint{//节点信息多的时候会习惯开个结构体来存 intdep,siz,son,top,fath; //点的深度子树大小重儿子所在重链的链头父亲节点 //没有重儿子则son=0 intid,l,r;//求lca不......
  • 树链剖分【产品说明书】
    一种暴论：树链剖分=多叉树上分块+线段树适用范围总之就是数据结构的基础问题。总的来说，树链剖分可以在\(O(m\logn)\)的时间复杂度中，解决大多数树上路径问题，包括其修改、维护和查询。例如这样的一道模板题又例如……（请直接跳到本文最后一章）产品简介树链剖分有两种：重......
  • 树链剖分
    树链剖分树链剖分常用于解决树上路径查询的问题。原理：对于树上两点之间的路径\(u\)->\(v\)，根据某种策略，将之拆分成若干条链，然后利用线段树等数据结构单独维护这些子链，最后将答案合并。常用的剖分方法：轻重边划分。剖分树种的边可以分为两种边：重边和轻边。设\(size_u\)......
  • 算法：树链剖分
    去年就看过树链剖分的视频了，当时连树状数组，线段树都没学，对树的dfs也一知半解，所以基本完全听不懂。昨天又重新看了一般，感觉思路挺简单，应该比线段树简单吧，从用树链剖分求LCA来看确实是这样的，但是没有想到的是用线段树维护树链剖分。QAQ这应该是我打过最长的代码吧！（3K）树链剖分......
  • 浅谈树链剖分—轻重链剖分
    闲话似乎会有很多种树剖，什么长链剖分之类的，但是暂时只会轻重链剖分（可怜）。以前的版本在这里，但是感觉写的太粗糙了，所以决定重写一篇（我也不知道为什么要一直写树剖而不写点别的）。正文引入如果给出一个序列，有一些区间修改查询之类的操作，直接上线段树什么的就完事了，但是如果给出的......
  • 树链剖分
    前言：本人太弱了，看着题解调了一下午，才A了树剖的板子题，所以写篇博客纪念一下（其实是怕自己忘了树剖怎么做）。本文以板子题为例子定义:树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个于且只属于一条链，然后再通过数据结构（树状数组、BST、SPL......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99