树链剖分之HLD
树链剖分之HLD
树链剖分的原理
对于数组这样的线性结构，要在其上实现区间查询（和与最值）、区间修改甚⾄是区间增删都是有办法的。例如、树状数组、线段树以及等。⽽树是⼀种⾮线性结构，为了⾼效的实现在树上的路径查询、路径修改操作，基本做法是将树按照某种⽅式剖成若⼲条链，再将这些链
按照顺序组成数组，最后在数组上采⽤线段树等⼿段实现操作。考虑如下⼀棵树：
可以把它剖成6条链，分别是、、、、和
，因此对应的新数组是
轻重边剖分
轻重边剖分（Heavy-light Decomposition）是树链剖分常⽤的⼀种⽅法，上⾯的例⼦就是⼀个HLD的例⼦。HLD可以⽤来解决⼀⼤类问题：在树的结构形态不发⽣变化的前提下，实现路径操作和⼦树操作（修改、查询和及最值）。
重⼉⼦：某个节点的⼦节点，其⼦树节点数量最⼤，则该⼦节点为该节点的重⼉⼦。其余为轻⼉⼦。在上例中，是的重⼉⼦，是的重⼉⼦，是的重⼉⼦。
重边：⽗节点和重⼉⼦之间的边称为重边。在上例中，、、都是重边。对应的，⽗节点和轻⼉⼦的边就称为轻边。重链：全部由重边构成的路径称为重链，⼜称为重路径。在上例中，、、、、和就是重链。个节点的树的任意⼀条路径上，最多只有条重链。每⼀条重链就是对应数组的⼀个连续的部分，因此其上的操作最多为。因此每次树上操作的时间为。
考虑每⼀次路径操作，我们需要知道路径到底是由哪些重链组成的以及这些重链在数组中对应的部分。路径上的重链信息显然是可以求出的，但是不必专门求出，在操作中不停更新重链即可。为了更新重链信息，对于每个节点还需记录深度信息以及每个节点所在重链的最顶层节点。深度信息⽐较容易理解。信息实际上就是每条链的第⼀个节点，例如在上例中的就是，的也是，⽽的则是。
有了和信息，即可进⾏路径操作。考虑之间的路径操作。因为和的不同，所以可以肯定不是⼀条重链。⼜因为的深度更深，所以可以肯定及其之间的重链全部都在路径上，可以进⾏⼀次区间操作；该次操作
完成以后就跳到节点，因为节点是的的⽗节点。再次考虑，因为的深度更深，所以全部在路径上，进⾏⼀次区间操作；然后跳到。、的相同，说明是最后⼀段区间，对其进⾏操作即可。
因为轻重边的区别完全取决于⼦树的节点数量，每个节点设置⼀个域，在⼀次深搜中就能确定的值，同时可以确定每个节点的重⼉⼦，以及每个节点的信息与⽗节点。确定重⼉⼦以后，再⼀次深搜就可以确定重链的顺序以及每个节点的。此次深搜的顺序即转化后的数组的索引序号，然后对该数组建树状数组或者线段树并进⾏操作即可。因此，整个解法复杂度为。其中为操作的总数量。
实现
是⼀个典型的树链剖分题⽬，树的形态维持不变，路径更新、单点查询，剖分完以后使⽤带延迟的线段树即可。
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include  <cstdio>
#include  <cstring>
#include  <algorithm>
using  namespace  std ;
#define  SIZE 50010
struct  edge_t {
int  node ;//另⼀个节点的编号
int  next ;//下⼀条边的地址，实际地址为Edge+next
}Edge [SIZE <<1];
ACHLN G IM BFK E DJ C A H C F B AC CH BF ACHLN G IM BFK E DJ N logN logN log N 2depth top top H top A L top A K top B depth top KM K M top KM M top M top C C M top KC K top BK A A C top AC size size depth top O (N +Qlog ——2N )Q
}Edge[SIZE<<1];
int ECnt =0;
int Vertex[SIZE];//邻接表表⽰所有的边
//a、b之间建⽴两条⽆向边
void mkEdge(int a,int b){
Edge[ECnt].node = b;
Edge[ECnt].next = Vertex[a];
Vertex[a]= ECnt ++;
Edge[ECnt].node = a;
Edge[ECnt].next = Vertex[b];
Vertex[b]= ECnt ++;
}
struct node_t{
int parent;//⽗节点
int heavy_son;//重边的⼦节点
int depth;//深度
int size;//size域
int top;//本节点所在的重链的最顶层节点
int nid;//在dfs重链时重新对节点编号，确保同⼀条链上的节点相邻
int weight;//权值，本题中即所求的数量
}Node[SIZE];
int TIdx =0;
int NewIdx[SIZE];//新编号到原树节点的映射
int N,M,P;
//dfs出所有重边，t为节点，parent为其⽗节点，depth为深度
/
/该dfs实际上确⽴了树的结构
void dfsHeavyEdge(int t,int parent,int depth){
Node[t].depth = depth;
Node[t].parent = parent;
Node[t].size =1;
//对t的所有⼦节点
for(int next=Vertex[t];next;next=Edge[next].next){
int u = Edge[next].node;
if( u == parent )continue;
dfsHeavyEdge(u,t,depth+1);
Node[t].size += Node[u].size;
/
/判断重边
if( Node[u].size > Node[Node[t].heavy_son].size )
Node[t].heavy_son = u;
}
}
//dfs出所有重链,t为节点，top为当前节点所在重链的最顶层节点
//重链实际上是以其顶层节点为标识保存的，任意节点都能够直接得出其所在重链的顶层节点void dfsHeavyPath(int t,int top){
Node[t].top = top;
Node[t].nid = TIdx++;
NewIdx[Node[t].nid]= t;
//t没有重⼉⼦，实际上就是叶节点
if(0== Node[t].heavy_son )return;
dfsHeavyPath(Node[t].heavy_son,top);
//对t的所有节点
for(int next=Vertex[t];next;next=Edge[next].next){
int u = Edge[next].node;
if( u == Node[t].parent
|| u == Node[t].heavy_son )continue;
dfsHeavyPath(u,u);
}
}
}
/
/带延迟的求区间和的线段树
struct stnode_t{
int peak;
int delay;
}ST[SIZE<<2];
inline int lson(int t){return t<<1;}
inline int rson(int t){return(t<<1)|1;}
void_pushUp(int t){ST[t].peak=ST[lson(t)].peak+ST[rson(t)].peak;} void_pushDown(int t){
if(0== ST[t].delay )return;
ST[lson(t)].delay += ST[t].delay;
ST[lson(t)].peak += ST[t].delay;
ST[rson(t)].delay += ST[t].delay;
ST[rson(t)].peak += ST[t].delay;
ST[t].delay =0;
}
//建树，递归建⽴节点
void build(int t,int s,int e){
ST[t].delay =0;
if( s == e ){
ST[t].peak = Node[NewIdx[s]].weight;
return;
}
int mid =( s + e )>>1;
build(lson(t),s,mid);
build(rson(t),mid+1,e);
_pushUp(t);
}
//[a,b]区间增加delta
void modify(int t,int s,int e,int a,int b,int delta){
if( a <= s && e <= b ){
ST[t].delay += delta;
ST[t].peak += delta;
return;
}
_pushDown(t);
int mid =( s + e )>>1;
if( a <= mid )modify(lson(t),s,mid,a,b,delta);
if( mid < b )modify(rson(t),mid+1,e,a,b,delta);
_pushUp(t);
}
//单点查询
int query(int t,int s,int e,int idx){
if( s == e )return ST[t].peak;
_pushDown(t);
int mid =( s + e )>>1;
int ret =( idx <= mid )
?query(lson(t),s,mid,idx)
:query(rson(t),mid+1,e,idx);
_pushUp(t);
return ret;
}
//关键操作，将原树上(x,y)路径的所有节点权值增加val
void change(int x,int y,int val){
//当x,y不处于同⼀条重链
while( Node[x].top != Node[y].top ){
/
cstring转为int/令x所处的重链总是更深
//令x所处的重链总是更深
if( Node[Node[x].top].depth < Node[Node[y].top].depth )
swap(x,y);
//将x所在的链的链顶到x的区间进⾏修改
modify(1,1,N,Node[Node[x].top].nid,Node[x].nid,val);
//将x修改为原链顶的⽗亲，实质上就是跳到了另外⼀条链
x = Node[Node[x].top].parent;
}
//到此处时，x、y处于同⼀条链，令x总是更浅，此举是为了确定左右区间if( Node[x].depth > Node[y].depth )swap(x,y);
//将x、y之间的路径更新
modify(1,1,N,Node[x].nid,Node[y].nid,val);
}
inline void init(){
ECnt = TIdx =1;
fill(Vertex,Vertex+N+1,0);
for(int i=0;i<=N;++i)Node[i].heavy_son =0;
}
bool read(){
if(EOF==scanf("%d%d%d",&N,&M,&P))
return false;
init();
for(int i=1;i<=N;++i)scanf("%d",&Node[i].weight);
for(int i=0;i<M;++i){
int a,b;
scanf("%d%d",&a,&b);
mkEdge(a,b);
}
//以第1个节点为根建树
dfsHeavyEdge(1,0,0);
//从根节点开始递归建重链
dfsHeavyPath(1,1);
//以ST[1]为根节点区间[1,N]建线段树
build(1,1,N);
return true;
}
char Cmd[5];
int main(){
while(read()){
while(P--){
scanf("%s",Cmd);
if('Q'==*Cmd ){
int x;
scanf("%d",&x);
printf("%d\n",query(1,1,N,Node[x].nid));
}else{
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
if('D'==*Cmd ) v =-v;
change(x,y,v);
}
}
}
return0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。