树剖学习笔记1 树链剖分模板【树链剖分】【树】【线段树】

作者: wjyyy 分类: 学习笔记,,线段树 发布时间: 2018-06-14 22:01

点击量:44

   弄懂树剖这方面各个数组的定义,并熟练掌握线段树,树链剖分就不是难事。

 

   我弄懂树链剖分是在教练的讲解和这篇文章的帮助下理解的,除了参考那篇文章,我再把重要的部分总结一下。

 

   我们要弄懂几个概念,重孩子是一个节点所有孩子中子树节点数量最多的那一个,连接父节点和重孩子的边叫做重链,树链剖分实际上是一种优化,它将树上最重要的,也就是最常经过的几条链划为重点,用线段树来优化区间修改和查询。并且因为在一棵子树中dfs序是连续的,并且在任意一条重链上,dfs序也是连续的,那么我们认为轻链是单点修改,重链是区间修改,对于这种轻重分明的结构,时间复杂度是被优化在\(O(Nlog^2N)\)的。

 

#include<cstdio>
#include<cstring>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)
int p;
int pnt[101000];
/***线段树开始***/
struct tnode
{
    int l,r,v,lazy;
    tnode(int l,int r,int v)
    {
        this->l=l;
        this->r=r;
        this->v=v;
        lazy=0;
    }
    tnode(int l,int r)
    {
        this->l=l;
        this->r=r;
        lazy=0;
    }
    tnode()
    {
        lazy=0;
    }
}t[432100];
int init[101000];
void build(int k,int l,int r)
{
    if(l==r)
    {
        t[k]=tnode(l,r,init[pnt[l]]);
        return;
    }
    t[k]=tnode(l,r);
    build(ls,l,mid);
    build(rs,mid+1,r);
    t[k].v=(t[ls].v+t[rs].v)%p;
    return;
}
void pushdown(int k)
{
    t[k].v+=t[k].lazy*(t[k].r-t[k].l+1);
    if(t[k].l!=t[k].r)
    {
        t[ls].lazy+=t[k].lazy;
        t[rs].lazy+=t[k].lazy;
    }
    t[k].v%=p;
    t[k].lazy=0;
    return;
}
void change(int k,int l,int r,int x)
{
    pushdown(k);
    if(l==t[k].l&&r==t[k].r)
    {
        t[k].lazy+=x;
        t[k].lazy%=p;
        return;
    }
    t[k].v+=x*(r-l+1);
    if(r<=Mid)
        change(ls,l,r,x);
    else if(l>Mid)
        change(rs,l,r,x);
    else
    {
        change(ls,l,Mid,x);
        change(rs,Mid+1,r,x);
    }
    t[k].v%=p;
    return;
}
int ask(int k,int l,int r)
{
    pushdown(k);
    if(t[k].l==l&&t[k].r==r)
        return t[k].v%p;
    if(r<=Mid)
        return ask(ls,l,r);
    else if(l>Mid)
        return ask(rs,l,r);
    else
        return (ask(ls,l,Mid)+
                ask(rs,Mid+1,r))%p;
}
/***线段树结束***/
/***链表+图开始***/
struct node
{
    int n;
    node *nxt;
    node(int n)
    {
        this->n=n;
        nxt=NULL;
    }
    node()
    {
        nxt=NULL;
    }
};
node head[101000],*tail[101000];
/***链表+图结束***/
/***dfs***/
int w[101000],top[101000];
int fa[101000],hs[101000];//分别存父亲和重儿子
int dfn[101000],cnt=0,over[101000];
int d[101000];
void dfs(int x)
{
    node *p=&head[x];
    int maxw=0;
    w[x]=1;
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(p->n==fa[x])
            continue;
        fa[p->n]=x;
        d[p->n]=d[x]+1;
        dfs(p->n);
        w[x]+=w[p->n];
        if(w[p->n]>maxw)
        {
            maxw=w[p->n];
            hs[x]=p->n;
        }
    }
    return;
}

void Dfs(int x,int t)
{
    dfn[x]=++cnt;
    pnt[cnt]=x;
    top[x]=t;
    node *p=&head[x];
    if(hs[x])
        Dfs(hs[x],t);
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(p->n==fa[x]||p->n==hs[x])
            continue;
        Dfs(p->n,p->n);
    }
    over[x]=cnt;
    return;
}
/***dfs结束***/
/***路径修改与查询***/
void modifyp(int x,int y,int z)
{
    int tx=d[top[x]],ty=d[top[y]];
    while(top[x]!=top[y])
    {
        if(tx<ty)//表示topy要深一些
        {
            change(1,dfn[top[y]],dfn[y],z);//top[y]是小于等于y的dfn
            y=top[y];
            y=fa[y];
        }
        else
        {
            change(1,dfn[top[x]],dfn[x],z);
            x=top[x];
            x=fa[x];//两头不相交,不重复修改
        }
        tx=d[top[x]];
        ty=d[top[y]];
    }
    if(dfn[x]<dfn[y])
    {
        int t=x;
        x=y;
        y=t;
    }
    change(1,dfn[y],dfn[x],z);
    return;
}

int path(int x,int y)
{
    int ans=0;
    int tx=d[top[x]],ty=d[top[y]];
    while(top[x]!=top[y])
    {
        if(tx<ty)
        {
            ans+=ask(1,dfn[top[y]],dfn[y]);
            ans%=p;
            y=top[y];
            y=fa[y];
        }
        else
        {
            ans+=ask(1,dfn[top[x]],dfn[x]);
            ans%=p;
            x=top[x];
            x=fa[x];
        }
        tx=d[top[x]];
        ty=d[top[y]];
    }
    if(dfn[x]<dfn[y])
    {
        int t=x;
        x=y;
        y=t;
    }
    ans+=ask(1,dfn[y],dfn[x]);
    return ans%p;
}
/***路径修改与查询结束***/
/***子树修改与查询***/
void modifyt(int x,int y)
{
    change(1,dfn[x],over[x],y);
}
int tree(int x)
{
    return ask(1,dfn[x],over[x])%p;
}
/***子树修改与查询结束***/
int main()
{
    memset(hs,0,sizeof(hs));
    int n,m,r,u,v,x,y,z;
    scanf("%d%d%d%d",&n,&m,&r,&p);
    for(int i=1;i<=n;i++)
    {
        tail[i]=&head[i];
        scanf("%d",&init[i]);
    }
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        tail[u]->nxt=new node(v);
        tail[u]=tail[u]->nxt;
        tail[v]->nxt=new node(u);
        tail[v]=tail[v]->nxt;
    }
    fa[r]=0;
    d[r]=1;
    dfs(r);
    Dfs(r,r);
    build(1,1,n);
    int opt;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&opt);
        switch(opt)
        {
            case 1:
                scanf("%d%d%d",&x,&y,&z);
                modifyp(x,y,z);
                break;
            case 2:
                scanf("%d%d",&x,&y);
                printf("%d\n",path(x,y));
                break;
            case 3:
                scanf("%d%d",&x,&y);
                modifyt(x,y);
                break;
            case 4:
                scanf("%d",&x);
                printf("%d\n",tree(x));
                break;
        }
    }
    return 0;
}

 

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 【树剖学习笔记】 […]

/* */