注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

树链剖分  

2016-12-15 14:01:28|  分类: 算法&数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
        树链剖分
        树链剖分,计算机术语,指一种对树进行划分的算法,它先通过轻重边剖分将树分为多条链,保证每个点属于且只属于一条链,然后再通过数据结构(树状数组、SBT、SPLAY、线段树等)来维护每一条链。
        用于解决树上的路径问题。
===============================
     Our protagonist is the handsome human prince Aragorn comes from The Lord of the Rings. One day Aragorn finds a lot of enemies who want to invade his kingdom. As Aragorn knows, the enemy has N camps out of his kingdom and M edges connect them. It is guaranteed that for any two camps, there is one and only one path connect them. At first Aragorn know the number of enemies in every camp. But the enemy is cunning , they will increase or decrease the number of soldiers in camps. Every time the enemy change the number of soldiers, they will set two camps C1 and C2. Then, for C1, C2 and all camps on the path from C1 to C2, they will increase or decrease K soldiers to these camps. Now Aragorn wants to know the number of soldiers in some particular camps real-time.
================================
        题目大意就是,在树上做一些操作:
        修改:树上两点路径上的所有点加上或减去一个值。
        询问:树上某点的值。
================================
        这,就是一道树剖裸题。树剖就是专门解决点对路径的问题。当然树剖只是负责找到点与点的路径,还要用到线段树或树状数组等数据结构维护。
        上面说了要通过轻重边剖分将树分为多条链,这样就可以把点对路径分成几条链(最多logn)再维护每条链(链是连续的!!)下面就来讲讲怎么划分链。
================================
定义:(资料来源:http://www.cnblogs.com/sagitta/p/5660749.htmlmaple的ppt
        当前节点的子节点中 子树大小最大的那个 ((如果有多个任取一个)——重儿子    启发式!!!
        不是重儿子的节点——轻儿子

        每个节点到重儿子的边——重(zhòng)边
        每个节点到轻儿子的边——轻边

        相连的重边是一条重链,轻链(也就是轻边)用于连接两条重链。

        重链轻链是相对而言的
如图:相连(连续的!!可以维护了!!)的红色边是一条重链,链接两条重链一条边是轻链。
树链剖分 - 杨鸿飞 - 杨鸿飞的博客
        这就是树剖。

        那如何修改/查询树上两点呢?

        两点在同一重链上:直接区间操作
        两点不在同一重链上:取树链的根的深度较大的那个点,从点到树链的根全部修改或更新答案,然后跳到树链的根的父亲节点,重新判断。
        这也只是很简单的树形维护。

        原理到此为止。时间复杂度?

        我们会发现这样一个性质:从任一节点向根节点走 走过的重链和轻边的条数都是log级别以内的维护一条链也是用到log级的维护,综合起来,修改/查询树上两点的复杂度为:logn^2

        证明如下:

        由于任一轻儿子对应的子树大小要小于父节点所对应子树大小的一半

        因此从一个轻儿子沿轻边向上走到父节点后 所对应的子树大小至少变为两倍以上

        经过的轻边条数自然是不超过log2N的

        然后由于重链都是间断的 ((连续的可以合成一条))
        所以经过的重链的条数是不超过轻边条数+1的

        因此经过重链的条数也是log级别的

        综合可知原命题得证.
==========================
        如何实现?任选一个结点做根,两个DFS或BFS!

        第一次搜索:求出每个结点的size(子树大小),father(父亲结点),deep(深度(到根节点距离)),son(儿子中size最大的做重儿子),不难。

DFS实现:

void SLPF_DFS1(int u,int father,int deep)
{
fa[u]=father; de[u]=deep; si[u]=1;

for (int kb=top[u]; kb!=-1; kb=e[kb].nx)
{
int v=e[kb].v;

if (v==father) continue;

SLPF_DFS1(v,u,deep+1); si[u]+=si[v];

if (son[u]==-1 || si[v]>si[son[u]]) son[u]=v; //选重儿子
}
}

BFS实现:

void SLPF_BFS1(int U,int father,int deep)
{
fa[U]=father; de[U]=deep; op[0]=U;

int Head,Tail;

for (Head=0,Tail=1; Head<Tail; Head++)
{
int u=op[Head];

for (int kb=top[u]; kb!=-1; kb=e[kb].nx)
{
int v=e[kb].v;

if (v==fa[u]) continue;

fa[v]=u; de[v]=de[u]+1; op[Tail++]=v;
}
}

for (int i=Tail-1; i>=0; i--) //从叶子到根递推
{
int v=op[i],u=fa[op[i]];

si[u]+=++si[v]; if (son[u]==-1 || si[v]>si[son[u]]) son[u]=v;
}
}



        第二次搜索:求出每个节点的point(映射到维护结构的位置(DFS序)),root(所在重链的根),要优先搜索重儿子!!

DFS实现:

void SLPF_DFS2(int u,int root)
{
p[u]=++tim; //时间戳

rt[u]=root;

if (son[u]==-1) return;

SLPF_DFS2(son[u],root); //优先搜素重儿子,使这条重链在维护结构的位置连续

for (int kb=top[u]; kb!=-1; kb=e[kb].nx)
{
int v=e[kb].v;

if (v!=son[u] && v!=fa[u]) SLPF_DFS2(v,v); //新的重链
}
}

BFS实现(自己想的,可能不是最好的写法,反正能对):

void SLPF_BFS2(int u)
{
op[0]=u;

for (int Head=0,Tail=1; Head<Tail; Head++)
{
int u=op[Head];

for (int s=u; s!=-1; s=son[s]) //直接遍历整条重链
{
p[s]=++tim; rt[s]=u;

for (int kb=top[s]; kb!=-1; kb=e[kb].nx)
{
int v=e[kb].v;

if (v==son[s] || v==fa[s]) continue;

op[Tail++]=v; //把沿途的重链的根入队
}
}
}
}


        如何查询?做法上面讲了。
实现:

void SLPF_Change(int p1,int p2,int del) //类似于倍增
{
while (rt[p1]!=rt[p2])
{
if (de[rt[p1]]>de[rt[p2]]) //谁的重链的根的深度较大就修改那段
{ Change(p[rt[p1]],p[p1],del); p1=fa[rt[p1]]; } //跳到下一条重链
else
{ Change(p[rt[p2]],p[p2],del); p2=fa[rt[p2]]; } //跳到下一条重链
}

if (de[p1]>de[p2]) Change(p[p2],p[p1],del); //最后两点一定在同一条重链上
else Change(p[p1],p[p2],del);
}

=========================
给出解决例题的程序:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>

#define lowbit(x) ( x & (-x) )
#define SC(a) for (int i=1; i<=n; i++) cout<<a[i]<<" "; cout<<endl;

using namespace std;

const int MLn=50010;
const int MLm=MLn*2;

struct Tedge { int v,nx; }e[MLm];

int top[MLn],tplb;

void ins(int u,int v)
{
int ntop=tplb++;

e[ntop].v=v; e[ntop].nx=top[u];

top[u]=ntop;
}

int fa[MLn],de[MLn],si[MLn],son[MLn],p[MLn],rt[MLn],tim;

void SLPF_DFS1(int u,int father,int deep)
{
fa[u]=father; de[u]=deep; si[u]=1;

for (int kb=top[u]; kb!=-1; kb=e[kb].nx)
{
int v=e[kb].v;

if (v==father) continue;

SLPF_DFS1(v,u,deep+1); si[u]+=si[v];

if (son[u]==-1 || si[v]>si[son[u]]) son[u]=v;
}
}

void SLPF_DFS2(int u,int root)
{
p[u]=++tim; rt[u]=root;

if (son[u]==-1) return;

SLPF_DFS2(son[u],root);

for (int kb=top[u]; kb!=-1; kb=e[kb].nx)
{
int v=e[kb].v;

if (v!=son[u] && v!=fa[u]) SLPF_DFS2(v,v);
}
}

int n;

int bi[MLn];

int Sum(int pp)
{
int sum=0;

for ( ; pp>0; pp-=lowbit(pp)) sum+=bi[pp];

return sum;
}

void Add(int pp,int del)
{
for ( ; pp<=n; pp+=lowbit(pp)) bi[pp]+=del;
}

void Change(int ll,int rr,int del) //树状数组实现(增加一段求一点!)
{
Add(ll,del); Add(rr+1,-del);
}

void SLPF_Change(int p1,int p2,int del)
{
while (rt[p1]!=rt[p2])
{
if (de[rt[p1]]>de[rt[p2]])
{ Change(p[rt[p1]],p[p1],del); p1=fa[rt[p1]]; }
else
{ Change(p[rt[p2]],p[p2],del); p2=fa[rt[p2]]; }
}

if (de[p1]>de[p2]) Change(p[p2],p[p1],del);
else Change(p[p1],p[p2],del);
}

void CSH()
{
memset(top,-1,sizeof top); tplb=0;
memset(son,-1,sizeof son); tim=0;
memset(bi,0,sizeof bi);
}

int a[MLn];

int main()
{
int m,q;

while ( ~scanf("%d%d%d",&n,&m,&q) )
{
CSH();

for (int i=1; i<=n; i++) scanf("%d",&a[i]);

for (int i=0; i<m; i++)
{
int u,v; scanf("%d%d",&u,&v);

ins(u,v); ins(v,u);
}

SLPF_DFS1(1,0,1); SLPF_DFS2(1,1);

for ( ; q>0; q--)
{
char ch; scanf("%s",&ch);

if (ch=='Q')
{
int xx; scanf("%d",&xx);

printf("%d\n",a[xx]+Sum(p[xx]));
}
else
{
int p1,p2,del; scanf("%d%d%d",&p1,&p2,&del);

if (ch=='D') del=-del;

SLPF_Change(p1,p2,del);
}
}
}

return 0;
}

代码实现巨长!!!不过不难写。

 


  评论这张
 
阅读(19)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018