树链剖分/重链剖分

咕咕嚕嚕 發表於 2025-4-26 12:38:00

<h2 id="什么是树链剖分重链剖分">什么是树链剖分/重链剖分</h2>
我们可以弄一道例题来看看： 
现在给定一棵 $n（1 \le n \le 10^5）$ 节点的树，每个节点上有一个数值，现在你可以进行 $m ( 1 \le m \le 10^5) $ 次操作。格式如下：
<ul>
<li><code>1 x z</code> 表示将 $x$ 到 $y$ 最短路径上的节点值加上 $z$ 。</li>
<li><code>2 x y</code> 表示树求 $x$ 到 $y$ 最短路径上的权值和。</li>
<li><code>3 x y</code> 将子树 $x$ 下的每个节点的权值加上 $y$ 。</li>
<li><code>4 x</code> 求子树 $x$ 下每个节点的权值之和。 
怎么写呢？当然，你需要前置知识线段树。接下来，且听我慢慢道来。</li>
</ul>
<h2 id="先从构造一个完美的剖分数组开始">先从构造一个完美的剖分数组开始</h2>
我们知道，一棵树可以通过DFS构造成一个序列，其中对于任意一棵子树（包括根节点），我们把他的节点个数叫做 $siz$ 。子树 $x$ 的大小就是 $siz_x$ 。那这对剖分有什么帮助呢？对于一棵树的DFS序举例如下：
<pre><code> 1
/ \
2 3
/
4
\
5
</code></pre>
那么DFS后，序列如下：
<pre><code>1 2 4 5 3
</code></pre>
可以看到，子树 $x$ 到 $x+siz_x$ ，就是整个子树 $x$ 。我们暂时叫这个数组为剖分数组 $tag$。但这样并不是最优的，有的的时候无法保证前面阐述的规律，这个时候怎么办呢？我们可以分析一下，在这棵树中，$1$ 有两个孩子，分别是 $2$ 和 $3$ ，而且 $2$ 的子树大小比 $3$ 大，那么我们就规定 $2$ 是 $1$ 的 重孩子 。从 $1$ 到 $2$ 的这条边我们叫做重链。可以得知，对于任意一个非叶子节点，都有其独有的重孩子，我们就可以根据重孩子来构造DFS的先后，因为我们优先遍历一棵树的所有重孩子，所以所有重孩子一定是连在一起的，上面就是一个说明。那优先从重孩子开始还有什么好处呢？我们知道，如果从轻孩子开始遍历去构造这个数组，那么时间复杂度可能会达到 $O(n)$（见后文）。但是如果从重孩子开始的话，就不一样了，我们可以证明其时间复杂度可以来到 $O(\log_2n)$ 的单次询问复杂度，证明如下： 
对于节点 $u$ ，其重孩子 $v$ 必然是所有子节点中子树最大的那个，即为:
<div class="math display">\[size(v) \ge size(w) \forall w \in children(u)
\]</div>又因为重孩子的子树大小 $\ge$ 其他所有子节点的子树大小，因此对于任意轻孩子 $w$ 有：
<div class="math display">\[size(w)\le size(v)
\]</div>又又因为所有节点子树个数+1等于其父亲节点的包含的节点个数（有点拗口），即为：
<div class="math display">\[size(v)+\sum_{轻孩子w} size(w)+1 = size(u)
\]</div>根据上面的第二,三条定理，解不等式方程，可以得到对于：
<div class="math display">\[\sum_{轻孩子w}size(w) \le size(u)-size(v)-1
\]</div>所以可以知道：如果某个轻孩子节点$w$ 的子树大小大于 $\frac{1}{2} size(u)$ , 则以上定理不成立，违背重孩子的定义，所以，必然有对于任意 $w$：
<div class="math display">\[size(w)\le \frac{size(u)}{2}
\]</div>因此，从根节点到任意节点得到路径上，最多只有 $O(\log n)$ 条轻边（因为每次碰到轻边子树大小随见到原来的 $\frac{1}{2}$ ,所以至多 $\log^2n$ 就会到达根节点） 
而又因为重孩子是连续的一段区间，所以一次线段树修改就可以，再加上轻边修改是每次 $O(\log n)$，最多 $\log n$ 条，所以是 $O(\log n)$ 时间复杂度，证毕。 
至此，我们的树链剖分的关键部分就已经完成。 
Code如下：
<pre><code class="language-cpp">void dfs1(int root, int fa) {
fath = fa;
siz = 1;
dep = dep + 1;
for(auto i : tree) {
 if(i == fa) continue;
 dfs1(i, root);
 siz += siz;
 if(siz > siz])
 son = i;
}
}

void dfs2(int root, int tp) {
top = tp;
dfn = ++cnt;
rev = root;
if(!son) return;
dfs2(son, tp);
for(auto i : tree) {
 if(i == fath || i == son) continue;
 dfs2(i, i);
}
}
</code></pre>
其中 <code>siz</code> 是表示大小，<code>top</code>表示链头（见后文），<code>dfn</code> 表示对于 $root$ 节点，在剖分数组里的位置。<code>rev</code> 是反的 <code>dfn</code>，<code>cnt</code> 全局计数器，<code>son</code> 记录重孩子编号，<code>dep</code> 表示深度。
<h2 id="利用链表的思想完成perfect的查询修改">利用链表的思想，完成perfect的查询/修改</h2>
我们已经知道，怎么分割一个有效的剖分数组。就是不会用，怎么办呢？ 
还是拿出一棵树：
<pre><code> 1
/ \
2 5
/ \ \
3 7 6
\ /
4 8
/ \
910
</code></pre>
构造出来的序列如下(<code>-</code>表示重链，<code> </code> 表示轻边）
<pre><code>1-2-3-4-9 10 7 5-6-8
</code></pre>
现在我们将 $10$ 到 $8$ 之间的，过程如下：
<ul>
<li>先使所有重链的链头为深度最小的节点，比如 $8,6,5$ 的链头都是 $5$，$9,4,3,2,1$ 的链头都是 $1$</li>
<li>令所有轻边的链头就是其本身 
那么修改的时候，每次选择深度大的条跳跃，直到两者链头相同。那么此时只需要修改当前 $\min{u,v}$ 到 $\max{u,v}$ （询问/操作的两个端点）就可以了！。 
到这里我们也可以知道了吧，按照轻边来的话时间复杂度是 $O(n)$ 的哦。千万小心！ 
因为查询和修改代码雷同，就不详细撰述了。</li>
</ul>
<h2 id="code-for-luogu-p3384">Code For Luogu P3384</h2>
<pre><code class="language-cpp">#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5+100;
int num,fath,top,son,dep,siz;
int lay,w,tag1,tag2,cnt,n,m,r,p;
vector<vector<int> > tree;

inline void dfs1(int root,int fa){
fath=fa;
siz=1;
dep=dep+1;
for(auto i : tree){
 if(i == fa)continue;
 dfs1(i,root);
 siz+=siz;
 if(siz>siz])
 son=i;
}
}

inline void dfs2(int root,int Top){
tag1=++cnt;
tag2=root;
top=Top;
if(son){
 dfs2(son,Top);
 for(auto i : tree){
 if(i == son || i==fath)continue;
 dfs2(i,i);
 }
}
}

void pushup(int root){
w=(w+w)%p;
}

void maketag(int root,int l,int r,int lz){
lay=(lay+lz)%p;
w=(w+(r-l+1)*lz)%p;
}

void pushdn(int root,int l,int r){
if(lay==0 || l==r) return;
int mid=(l+r)>>1;
maketag(root<<1,l,mid,lay);
maketag(root<<1|1,mid+1,r,lay);
lay=0;
}

void build(int root,int l,int r){
if(l==r){
 w=num]%p;
 return ;
}
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
pushup(root);
}

int query(int root,int l,int r,int L,int R){
if(R<l || L>r) return 0;
if(L<=l && r<=R) return w;
pushdn(root,l,r);
int mid=(l+r)>>1;
return (query(root<<1,l,mid,L,R)+query(root<<1|1,mid+1,r,L,R))%p;
}

void update(int root,int l,int r,int L,int R,int val){
if(R<l || L>r) return;
if(L<=l && r<=R){
 maketag(root,l,r,val);
 return;
}
pushdn(root,l,r);
int mid=(l+r)>>1;
update(root<<1,l,mid,L,R,val);
update(root<<1|1,mid+1,r,L,R,val);
pushup(root);
}

void udp(int x,int y,int val){
while(top!=top){
 if(dep]<dep]) swap(x,y);
 update(1,1,n,tag1],tag1,val);
 x=fath];
}
if(dep>dep) swap(x,y);
update(1,1,n,tag1,tag1,val);
}

int qry(int x,int y){
int ans=0;
while(top!=top){
 if(dep]<dep]) swap(x,y);
 ans=(ans+query(1,1,n,tag1],tag1))%p;
 x=fath];
}
if(dep>dep) swap(x,y);
ans=(ans+query(1,1,n,tag1,tag1))%p;
return ans;
}

signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

cin>>n>>m>>r>>p;
tree.resize(n+1);
for(int i=1;i<=n;i++) cin>>num;
for(int i=1;i<n;i++){
 int x,y;
 cin>>x>>y;
 tree.push_back(y);
 tree.push_back(x);
}
dfs1(r,0);
dfs2(r,r);
build(1,1,n);
for(int i=1;i<=m;i++){
 int op,x,y,z;
 cin>>op;
 if(op==1){
 cin>>x>>y>>z;
 udp(x,y,z);
 }
 else if(op==2){
 cin>>x>>y;
 cout<<qry(x,y)<<endl;
 }
 else if(op==3){
 cin>>x>>z;
 update(1,1,n,tag1,tag1+siz-1,z);
 }
 else if(op==4){
 cin>>x;
 cout<<query(1,1,n,tag1,tag1+siz-1)<<endl;
 }
}
return 0;
}
</code></pre>
线段树部分请自学哦！
<h2 id="完美的习题">完美的习题</h2>
<ul>
<li>P3384 【模板】重链剖分/树链剖分</li>
<li>P3258 松鼠的新家</li>
</ul> 
来源：https://www.cnblogs.com/CheeseFunction/p/18847884

頁: [1]

琼殿技术论坛's Archiver

树链剖分/重链剖分