啊哈树链剖分——重链剖分（之后学完splay就搞虚实链剖分）

蔚落 2022-11-28 10:36 164阅读 0赞

阿巴阿巴阿巴。。。。后续会加splay+虚实链剖分

学习博客：[https://blog.csdn.net/qq\_43326267/article/details/89791152][https_blog.csdn.net_qq_43326267_article_details_89791152]

讲挺好的（我还自信的以为他的某个地方有问题，结果自己debug半天，发现就是我以为有问题的地方其实没问题，改了半天的bug）

其实不难的就是把之前学的东西糅合一下

其实就是把一个树通过重链放成一排，然后线段树维护，对于一条重链（对应线段树部分为连续区间），可以直接区间修改（查询）,不同重链可以通过跳链头来到同一条链

性质：每个点都在某条重链上，且不会出现某个点在两条重链上

定义：

重儿子：子树节点最多的儿子

重链：由重儿子组成的链

树上两点路径为深点不断跳到链头父亲节点，直到在一条链上（等同于线段树连续段上）

子树为一连续区间段，dfs建链的时候存最后一个节点的值就可以了

开的数组较多，需要对之前的dfs建树和线段树有着较高的熟练度和理解，不然修bug你会烦死的

例题：洛谷树链板子题：[https://www.luogu.com.cn/problem/P3384][https_www.luogu.com.cn_problem_P3384]

AC代码

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+7;
    typedef long long ll;
    #define int ll
    #define FOPEN freopen("C:\\Users\\l\\Downloads\\P3384_1.in","r",stdin)
    int n,q,rt;
    int a[N];
    int mod;
    int dep[N];
    int siz[N];
    int fa[N],er[N],cnt;
    int top[N];///链头
    int dfn[N],id[N];///访问顺序双向映射
    int tot[N];///回溯标记子树最大编号
    int tree[N*4],lazy[N*4],num[N*4];
    vector<int>son[N];
    void init();
    void dfs1(int x)
    {
        siz[x]=1;
        for(int i=0;i<son[x].size();i++)
        {
            int d=son[x][i];
            if(d==fa[x]) continue;
            fa[d]=x;
            dep[d]=dep[x]+1;
            dfs1(d);
            siz[x]+=siz[d];
            if(siz[d]>siz[er[x]]) er[x]=d;
        }
    }
    void dfs2(int x,int tp)
    {
        top[x]=tp;
        dfn[x]=++cnt;
        id[cnt]=x;
        if(er[x]) dfs2(er[x],tp);
        for(int i=0;i<son[x].size();i++)
        {
            int d=son[x][i];
            if(d==fa[x]||d==er[x]) continue;
            dfs2(d,d);
        }
        tot[x]=cnt;
    }
    void build(int l,int r,int rt)
    {
        if(l==r)
        {
           // cout<<l<<' '<<rt<<' '<<id[l]<<endl;
            tree[rt]=a[id[l]];
            num[rt]=1;
            return;
        }
        int mid=(l+r)/2;
        build(l,mid,rt*2);
        build(mid+1,r,rt*2+1);
        tree[rt]=tree[rt*2]+tree[rt*2+1];
        num[rt]=num[rt*2]+num[rt*2+1];
    }
    void update(int l,int r,int rt,int L,int R,int x)
    {
        if(l>=L&&r<=R)
        {
            lazy[rt]+=x;
            return;
        }
        if(lazy[rt])
        {
            lazy[rt*2]+=lazy[rt];
            lazy[rt*2+1]+=lazy[rt];
            lazy[rt]=0;
        }
        int mid=(l+r)/2;
        if(mid>=L) update(l,mid,rt*2,L,R,x);
        if(mid<R) update(mid+1,r,rt*2+1,L,R,x);
         tree[rt]=tree[rt*2]+tree[rt*2+1]+num[rt*2]*lazy[rt*2]+num[rt*2+1]*lazy[rt*2+1];
    }
    int query(int l,int r,int rt,int L,int R)
    {
        int ans=0;
        if(l>=L&&r<=R)
        {
            return tree[rt]+lazy[rt]*num[rt];
        }
         if(lazy[rt])
        {
            lazy[rt*2]+=lazy[rt];
            lazy[rt*2+1]+=lazy[rt];
            lazy[rt]=0;
        }
        int mid=(l+r)/2;
        if(mid>=L) ans+=query(l,mid,rt*2,L,R);
        ans%=mod;
        if(mid<R) ans+=query(mid+1,r,rt*2+1,L,R);
         tree[rt]=tree[rt*2]+tree[rt*2+1]+num[rt*2]*lazy[rt*2]+num[rt*2+1]*lazy[rt*2+1];
         return ans%mod;
    }
    void cao1()
    {
        int x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        while(top[x]!=top[y])
        {
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            update(1,n,1,dfn[top[x]],dfn[x],z);
            x=fa[top[x]];
        }
        if(dep[x]<dep[y]) swap(x,y);
        update(1,n,1,dfn[y],dfn[x],z);
        //for(int i=1;i<=9;i++) cout<<tree[i]<<' ';cout<<endl;
        //for(int i=1;i<=9;i++) cout<<lazy[i]<<' ';cout<<endl;
    }
    void cao2()
    {
        int x,y;
        int ans=0;
        scanf("%lld%lld",&x,&y);
        while(top[x]!=top[y])
        {
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            ans+=query(1,n,1,dfn[top[x]],dfn[x]);
            //cout<<dfn[top[x]]<<' '<<dfn[x]<<' '<<x<<' '<<y<<endl;
            x=fa[top[x]];
            ans%=mod;
        }
        if(dep[x]<dep[y]) swap(x,y);
        ans+=query(1,n,1,dfn[y],dfn[x]);
        //cout<<dfn[x]<<' '<<dfn[x]<<' '<<x<<' '<<y<<endl;
        printf("%lld\n",ans%mod);
       // for(int i=1;i<=9;i++) cout<<tree[i]<<' ';cout<<endl;
       // for(int i=1;i<=9;i++) cout<<lazy[i]<<' ';cout<<endl;
    }
    void cao3()
    {
        int x,z;
        scanf("%lld%lld",&x,&z);
        //cout<<dfn[x]<<' '<<tot[x]<<endl;
        update(1,n,1,dfn[x],tot[x],z);
        //for(int i=1;i<=9;i++) cout<<tree[i]<<' ';cout<<endl;
        //for(int i=1;i<=9;i++) cout<<lazy[i]<<' ';cout<<endl;
    }
    void cao4()
    {
        int x;
        scanf("%lld",&x);
        printf("%lld\n",query(1,n,1,dfn[x],tot[x])%mod);
        //for(int i=1;i<=9;i++) cout<<tree[i]<<' ';cout<<endl;
        //for(int i=1;i<=9;i++) cout<<lazy[i]<<' ';cout<<endl;
    }
    void solve()
    {
        while(q--)
        {
            int op;
            scanf("%lld",&op);
            switch(op)
            {
            case 1:
                cao1();break;
            case 2:
                cao2();break;
            case 3:
                cao3();break;
            case 4:
                cao4();break;
            }
        }
    }
    signed main()
    {
        //FOPEN;
        init();
        solve();
    }
    void init()
    {
        scanf("%lld%lld%lld%lld",&n,&q,&rt,&mod);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        for(int i=1;i<n;i++)
        {
            int a1,a2;
            scanf("%lld%lld",&a1,&a2);
            son[a1].push_back(a2);
            son[a2].push_back(a1);
        }
        dfs1(rt);
        dfs2(rt,rt);
        build(1,n,1);
       //cout<<cnt<<endl;
        //for(int i=1;i<=n;i++) cout<<dfn[i]<<' ';cout<<endl;
        //for(int i=1;i<=n;i++) cout<<id[i]<<' ';cout<<endl;
    
        //for(int i=1;i<=9;i++) cout<<tree[i]<<' ';cout<<endl;
    
    }

例题\*2

牛客第7场C

三种操作 1 . x点+w 其余点y +w-dist(x,y)（与x点最短边数）

2. 某个点w变为0 如果比0小就不用变

3.查询某点w

吧所有的1操作的权值修改放到根节点去，路径区间修改每个点+2

这样每个点的w就是路径区间和+根节点权值-dep\[x\]\*num(多少次1操作)

[https_blog.csdn.net_qq_43326267_article_details_89791152]: https://blog.csdn.net/qq_43326267/article/details/89791152
[https_www.luogu.com.cn_problem_P3384]: https://www.luogu.com.cn/problem/P3384