树链剖分学习-白红宇

树链剖分学习

阅读量：4572 次

发布时间：2019-06-08

本文共 3911 字，大约阅读时间需要 13 分钟。

近期学习树链剖分，在网上搜了非常多文章，这里推荐一篇博客：。

这篇博客讲的非常细致。在了解了基本原理之后，能够学习一下kuangbin大大的模板：

定义部分：

struct Edge{    int to,next;}edge[2*maxn];//树的边int head[maxn],tot;//邻接表int top[maxn];//节点所在重链的最高点int fa[maxn];//节点的父亲节点int deep[maxn];//节点的深度int num[maxn];//节点子树的节点数int p[maxn];//p与父节点间连线在线段树中的位置int fp[maxn];//线段树中fp位置相应的的节点int tson[maxn];//重儿子int pos;//线段树中的位置

初始化部分：

void init()   //初始化操作{    tot=1;    memset(head,-1,sizeof(head));    pos=1;    memset(tson,-1,sizeof(tson));}

邻接表的加边操作：

void addedge(int u,int v)     //邻接表的加边操作{    edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;}

以下就是两个重点操作：1.求fa,deep,son,num 2.求top,p

void  dfs(int u,int pre,int d) //求fa,deep,son,num{    fa[u]=pre;    deep[u]=d;    num[u]=1;    for(int i=head[u];i!=-1;i=edge[i].next)    {        int v=edge[i].to;        if(v!=pre)        {            dfs(v,u,d+1);            num[u]+=num[v];            if(tson[u]==-1||num[tson[u]]

以下这个是依据题目而订的操作，就是訪问u->v链，并运行操作：

void Change(int u,int v,int value)  //区间更新{    int f1=top[u],f2=top[v];    while(f1!=f2)    {        if(deep[f1]

注意：树链剖分能够分为两种，一种是边权处理，一种是点权处理。点权处理没什么好说的，边权处理时，我们用儿子节点代表该节点与父节点之间的边的权值。

hdu 3966 Aragorn's Story（点权）

这道题使用的是树链剖分+树状数组，注意查询t节点时，查询的是p[t]（常常忘记，WA了好几次 = =。）

#pragma comment(linker, "/STACK:1024000000,1024000000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #define maxn 50010using namespace std;typedef long long ll;struct Edge{ int to,next;}edge[2*maxn];//树的边int head[maxn],tot;//邻接表int top[maxn];//节点所在重链的最高点int fa[maxn];//节点的父亲节点int deep[maxn];//节点的深度int num[maxn];//节点子树的节点数int p[maxn];//p与父节点间连线在线段树中的位置int fp[maxn];//线段树中fp位置相应的的节点int tson[maxn];//重儿子int pos;//线段树中的位置void init() //初始化操作{ tot=1; memset(head,-1,sizeof(head)); pos=1; memset(tson,-1,sizeof(tson));}void addedge(int u,int v) //邻接表的加边操作{ edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;}void dfs(int u,int pre,int d) //求fa,deep,son,num{ fa[u]=pre; deep[u]=d; num[u]=1; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v!=pre) { dfs(v,u,d+1); num[u]+=num[v]; if(tson[u]==-1||num[tson[u]]
             
              0) { sum+=son[d]; d-=lowbit(d); } return sum;}void Change(int u,int v,int value) //区间更新{ int f1=top[u],f2=top[v]; while(f1!=f2) { if(deep[f1]

SPOJ QTREE（边权）树链剖分+线段树

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #define maxn 10010#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;typedef long long ll;struct Edge{ int to,next;}edge[2*maxn];//树的边int head[maxn],tot;//邻接表int top[maxn];//节点所在重链的最高点int fa[maxn];//节点的父亲节点int deep[maxn];//节点的深度int num[maxn];//节点子树的节点数int p[maxn];//p与父节点间连线在线段树中的位置int fp[maxn];//线段树中fp位置相应的的节点int tson[maxn];//重儿子int pos;//线段树中的位置void init() //初始化操作{ tot=1; memset(head,-1,sizeof(head)); pos=1; memset(tson,-1,sizeof(tson));}void addedge(int u,int v) //邻接表的加边操作{ edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;}void dfs(int u,int pre,int d) //求fa,deep,son,num{ fa[u]=pre; deep[u]=d; num[u]=1; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v!=pre) { dfs(v,u,d+1); num[u]+=num[v]; if(tson[u]==-1||num[tson[u]]
             
              m) Update_n(w,l,r,rt<<1|1); else { Update_n(w,lson); Update_n(w,rson); } PushUp(rt);}int Query(int l,int r,int rt){ if(son[rt].l==l&&son[rt].r==r) { return son[rt].value; } //PushDown(rt); int ret=0; int m=(son[rt].l+son[rt].r)/2; if(r<=m) ret=Query(l,r,rt<<1); else if(l>m) ret=Query(l,r,rt<<1|1); else { ret=Query(lson); ret=max(Query(rson),ret); } return ret;}int find(int u,int v) //寻找u->v的链上的最值{ //主要思想就是比較u和v的是否在同一条重链上 int f1=top[u],f2=top[v];//若在同一条重链上（f1=f2），直接求就能够了 int tmp=0; //由于同一条重链上的点在线段树中是连续的 while(f1!=f2) //若不在同一条重链上。那么我们比較两个点的深度 { //一直向上寻找，直到连个点在同一条重链上 if(deep[f1]