@xzyxzy 2018-04-01T17:14:57.000000Z 字数 3575 阅读 1366

树链剖分

数据结构

一、概念

把树剖成链再操作
博客安利：http://www.cnblogs.com/chinhhh/p/7965433.html

二、实现

方法

维护7个不同数组，通常和线段树一起使用

复杂度

首先两次DFS为 $NlogN$
然后每个询问，查询子树是 $logN$ ，线段树查询路径权值和等一般要求LCA，为 $log^{2}N$
线段树贡献了一个 $logN$
综上为 $O(NlogN+Qlog^{2}N)$
但实际上自带小常数，远不及log方

三、适用范围

维护树上两点之间的路径（带修改）
维护树上一棵子树的权值（带修改）

四、题目

1、模板题

2、应用题

四、做题经验

1、线段树加法进行下放懒标记和打标记时要乘区间长度

    if(l>=gl&&r<=gr)
    {
        t[now]=(t[now]+(r-l+1)*z)%P;
        lazy[now]=(lazy[now]+z)%P;
        return;
    }

    t[now<<1]=(t[now<<1]+lazy[now]*(mid-l+1))%P;
    t[now<<1|1]=(t[now<<1|1]+lazy[now]*(r-mid))%P;

这是P3384 模板，当时还请zsy帮忙调了

2、把边权下放到点权的时候注意临界情况

    if(Query(1,1,n,dfn[y]+1,dfn[x]))printf("No\n");

这是P3950 部落冲突，把边下放到点的时候，对于LCA特殊处理，比如说点A和B的LCA是K，K上方发生战争于是标记在K，但A和B还是联通的，所以查询时要忽略K，即+1。

3、注意lazy是非零即放，那么不要打叹号

查错时可以考虑一下

4、注意这一段

    if(deep[top[x]]<deep[top[y]])swap(x,y);

不是这个

    if(deep[x]<deep[y])swap(x,y);

附录

//P3384 模板
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define ll long long 
using namespace std;
ll read()
{
    char ch=getchar();
    ll h=0,t=1;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-'){ch=getchar();t=-1;}
    while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
    return h*t;
}
const ll MAXN=500001;
ll head[MAXN],cnt=0;
struct edge{ll next,to;}a[MAXN<<1];
void link(ll x,ll y){a[++cnt]=(edge){head[x],y};head[x]=cnt;}
ll N,M,Root,P;
ll top[MAXN],fa[MAXN],deep[MAXN],son[MAXN];
ll dfn[MAXN],size[MAXN],id[MAXN],tot;
void DFS1(ll x)
{
    deep[x]=deep[fa[x]]+1;size[x]=1;
    for(ll i=head[x];i!=-1;i=a[i].next)
    {
        ll R=a[i].to;
        if(R==fa[x])continue;
        fa[R]=x;DFS1(R);
        size[x]+=size[R];
        if(size[R]>size[son[x]])son[x]=R;
    }
}
void DFS2(ll x)
{
    dfn[x]=++tot;id[tot]=x;
    if(son[fa[x]]==x)top[x]=top[fa[x]];
    else top[x]=x;
    if(son[x])DFS2(son[x]); 
    for(ll i=head[x];i!=-1;i=a[i].next)
        if(a[i].to!=fa[x]&&a[i].to!=son[x])DFS2(a[i].to);
}
ll t[MAXN<<2],lazy[MAXN<<2],f[MAXN];
void Buildtree(ll now,ll l,ll r)
{
    if(l==r){t[now]=f[id[l]];lazy[now]=0;return;}
    ll mid=(l+r)>>1;
    Buildtree(now<<1,l,mid);
    Buildtree(now<<1|1,mid+1,r);
    t[now]=t[now<<1]+t[now<<1|1];
}
void Pushdown(ll now,ll l,ll r,ll mid)
{
    ll W=lazy[now];lazy[now]=0;
    t[now<<1]=(t[now<<1]+W*(mid-l+1))%P;
    t[now<<1|1]=(t[now<<1|1]+W*(r-mid))%P;
    lazy[now<<1]=(lazy[now<<1]+W)%P;
    lazy[now<<1|1]=(lazy[now<<1|1]+W)%P;
}
void Add(ll now,ll l,ll r,ll gl,ll gr,ll z)
{
    if(l>gr||r<gl)return;
    if(l>=gl&&r<=gr){t[now]=(t[now]+(r-l+1)*z)%P;lazy[now]=(lazy[now]+z)%P;return;}
    ll mid=(l+r)>>1;
    if(lazy[now])Pushdown(now,l,r,mid);
    Add(now<<1,l,mid,gl,gr,z);
    Add(now<<1|1,mid+1,r,gl,gr,z);
    t[now]=(t[now<<1]+t[now<<1|1])%P;
}
ll Query(ll now,ll l,ll r,ll gl,ll gr)
{
    if(l>gr||r<gl)return 0;
    if(l>=gl&&r<=gr)return t[now];
    ll mid=(l+r)>>1;
    if(lazy[now])Pushdown(now,l,r,mid);
    return (Query(now<<1,l,mid,gl,gr)+Query(now<<1|1,mid+1,r,gl,gr))%P;
}
void Work_A()
{
    ll x=read(),y=read(),z=read()%P;
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        Add(1,1,N,dfn[top[x]],dfn[x],z);
        x=fa[top[x]];
    }
    if(deep[x]<deep[y])swap(x,y);
    Add(1,1,N,dfn[y],dfn[x],z);
}
void Work_B()
{
    ll x=read(),y=read(),ans=0;
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        ans=(ans+Query(1,1,N,dfn[top[x]],dfn[x]))%P;
        x=fa[top[x]];
    }
    if(deep[x]<deep[y])swap(x,y);
    ans=(ans+Query(1,1,N,dfn[y],dfn[x]))%P;
    printf("%d\n",ans);
}
void Work_C()
{
    ll x=read(),z=read()%P;
    Add(1,1,N,dfn[x],dfn[x]+size[x]-1,z);
}
void Work_D()
{
    ll x=read(),ans=Query(1,1,N,dfn[x],dfn[x]+size[x]-1);
    printf("%d\n",ans);
}
int main()
{
    N=read();M=read();Root=read();P=read();
    memset(head,-1,sizeof(head));
    for(ll i=1;i<=N;i++)f[i]=read();
    for(ll i=1;i<=N-1;i++)
    {
        ll x=read(),y=read();
        link(x,y);link(y,x);
    }
    DFS1(Root);DFS2(Root);
    Buildtree(1,1,N);
    for(ll i=1;i<=M;i++)
    {
        ll kind=read();
        if(kind==1)Work_A();
        if(kind==2)Work_B();
        if(kind==3)Work_C();
        if(kind==4)Work_D();
    }
    return 0;
}