树链剖分笔记

树链剖分+线段树代码量通常在3K左右，出错的地方非常多，为了好好练手，特建立该题单，建议不要进行复制每一题都老老实实重打

题单 博客 题单Orz

1. 区间加，区间修改，区间最大值

#include<bits/stdc++.h>
using namespace std;const int MX=1e5+10;
int n,m,r,p;int input[MX]={0};int siz[MX]={0};int fath[MX]={0};int top[MX]={0};int dfn[MX]={0};int son[MX]={0};int high[MX]={0};int w[MX]={0};
//线段树好闪，拜谢线段树
struct node{
    long long sum;
    long long lc,rc;
    long long lazy;
}tree[MX<<1];
long long cnt=1,root=1;
inline void update(long long now){
    tree[now].sum=tree[tree[now].lc].sum+tree[tree[now].rc].sum;
}
inline void addnode(long long &now,long long l,long long r,long long val){
    if(now==0)  now=++cnt;
    tree[now].sum+=((r-l+1)*val)%p;tree[now].sum%=p;
    tree[now].lazy+=val%p;tree[now].lazy%=p;
}
inline void pushdown(long long now,long long l,long long r){
    if(l>=r)  return;
    long long mid=(r+l-1)>>1;
    addnode(tree[now].lc,l,mid,tree[now].lazy);
    addnode(tree[now].rc,mid+1,r,tree[now].lazy);
    tree[now].lazy=0;
}
void add(long long now,long long lt,long long rt,long long l,long long r,long long val){
    if(lt>r||l>rt)  return;
    if(l<=lt&&rt<=r){
        addnode(now,lt,rt,val);
        return ;
    }
    long long mid=(rt+lt-1)>>1;pushdown(now,lt,rt);
    add(tree[now].lc,lt,mid,l,r,val);add(tree[now].rc,mid+1,rt,l,r,val);
    update(now);
    return ;
}
long long cy(long long now,long long lt,long long rt,long long l,long long r){
    if(lt>r||l>rt)  return 0;
    if(l<=lt&&rt<=r){
        return tree[now].sum;
    }
    long long mid=(rt+lt-1)>>1;pushdown(now,lt,rt);
    return (cy(tree[now].lc,lt,mid,l,r)+cy(tree[now].rc,mid+1,rt,l,r))%p;
}
void build_t(){
    for(int i=1;i<=n;i++){
        add(root,1,n,i,i,w[i]);
    }
}
/*
int siz[MX]={0};    大小
int fa[MX]={0};     父亲
int top[MX]={0};    重链开始的地方
int dfn[MX]={0};    DFS序
int son[MX]={0};   重儿子
int high[MX]={0};  高度
int w[MX]={0};     时间戳权值
*/
vector<int> vec[MX];
void dfs1(int now,int fa){//确定  大小，父亲，高度，重儿子
    siz[now]=1,fath[now]=fa,high[now]=high[fa]+1;
    int maxn=-0x3f3f3f3f;
    for(auto to:vec[now]){
        if(to==fa)  continue;
        dfs1(to,now);
        siz[now]+=siz[to];
        if(maxn<siz[to]){
            maxn=siz[to];
            son[now]=to;
        }
    }
}
int tim=0;

//  now ：当前节点
//  fa  ：重链开头(并不是父节点)
void dfs2(int now,int fa){//确定重链开头，时间戳，dfs序
    dfn[now]=++tim;
    top[now]=fa;
    w[tim]=input[now];
    if(!son[now])  return;    //没有重儿子就是叶子节点
    dfs2(son[now],fa);//先走重儿子
    for(auto to:vec[now]){
        if(to==fath[now]||to==son[now])  continue;
        dfs2(to,to);//不在fa的重链上，所以to重链的开头是自己
    }
}

int main(){
    scanf("%d%d%d%d",&n,&m,&r,&p);
    for(int i=1;i<=n;i++){
        scanf("%d",&input[i]);
    }
    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        vec[x].push_back(y);vec[y].push_back(x);
    }
    dfs1(r,r);
    dfs2(r,r);
    build_t();
    for(int i=1;i<=m;i++){
        int op;scanf("%d",&op);
        if(op==1){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            z%=p;
            while(top[x]!=top[y]){
                if(high[top[x]]<high[top[y]]){
                    swap(x,y);
                }
                add(root,1,n,dfn[top[x]],dfn[x],z);
                x=fath[top[x]];
            }
            if(high[x]>high[y])  swap(x,y);
            add(root,1,n,dfn[x],dfn[y],z);
        }
        else if(op==2){
            int x,y;
            scanf("%d%d",&x,&y);
            int sum=0;
            while(top[x]!=top[y]){
                if(high[top[x]]<high[top[y]])  swap(x,y);
                sum=(sum+cy(root,1,n,dfn[top[x]],dfn[x]))%p;
                x=fath[top[x]];
            }
            if(high[x]>high[y])  swap(x,y);
            sum=(sum+cy(root,1,n,dfn[x],dfn[y]))%p;
            printf("%d\n",sum%p);
        }
        else if(op==3){
            int x,z;
            scanf("%d%d",&x,&z);
            add(root,1,n,dfn[x],dfn[x]+siz[x]-1,z);
        }
        else{
            int x;
            scanf("%d",&x);
            printf("%d\n",cy(root,1,n,dfn[x],dfn[x]+siz[x]-1));
        }
    }

    return 0;
}

每次都直接重新打,在你吐之前一定能够熟练掌握这个算法！！