树链剖分 时间！！！！

首先要学会线段树。由于线段树是基本技能，所以不再此过多解释。

 

树链剖分操作如下

操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z

操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和

操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z

操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和

 

还有几个概念：重儿子，轻儿子，重链，轻链。

众所周知，以每一个节点为根节点下所成的树（语文技能崩溃）都有一个大小（节点的数量）

如果有一个儿子体型（节点数）在所有兄弟姐妹中最大，那么这个儿子就是这个节点的重儿子；

其他的儿子都是轻儿子。

重边就是每两个重儿子之间的边（手拉手，我们都是重儿子）；轻边就是剩下的；

重链就是相邻的每个重边连起来的链，包括一条端点重儿子和轻儿子之间的边，也就是所有重链以一个轻儿子开始；

 

看完定义该干事了！！！

首先，处理dep[],fa[],siz[],son[]

 

void dfs1(int u,int fa){    f[u]=fa;//记录u节点的父亲     siz[u]=1;//子树大小，包括他自己     dep[u]=dep[fa]+1;//深度     for(int p=last[u];p;p=pre[p])    {        int v=other[p];        if(v==fa) continue;        dfs1(v,u);        siz[u]+=siz[v];        if(siz[v]>siz[son[u]]) son[u]=v;//记录重儿子         }}

second 新编，赋值，找头，先重再轻

因为先处理重儿子就会让重儿子之间的编号是连续的。

void dfs2(int u,int tp){    id[u]=++cnt;//重新编号     top[u]=tp;//这个点所在链的顶端     b[cnt]=a[u];//新编号赋值    if(!son[u]) return ;//no son    dfs2(son[u],tp);    for(int p=last[u];p;p=pre[p])    {        int v=other[p];        if(v==son[u]||v==f[u]) continue;        dfs2(v,v);//对于每一个轻儿子都有一条从它自己开始的链     }    }

 

third 套用线段树。

 

代码：

#include
     
      #include
      
       #include
       
        using namespace std;const int maxn=100050;int n,m,s,mo,a[maxn];int pre[maxn*2],other[maxn*2],last[maxn],l;int f[maxn],siz[maxn],dep[maxn],son[maxn];int id[maxn],cnt,top[maxn],b[maxn];void add(int x,int y){    l++;    pre[l]=last[x];    last[x]=l;    other[l]=y;}//下面是线段树 struct tree{    int l,r;    int sum,lazy;}t[4*maxn];//四倍，前人的经验 void build(int x,int l,int r)//建树 {    t[x].l=l;t[x].r=r;    if(l==r)    {        t[x].sum=b[l];        return ;    }    int mid=(l+r)>>1;    build(2*x,l,mid);    build(2*x+1,mid+1,r);    t[x].sum=(t[2*x].sum+t[2*x+1].sum)%mo;}void update(int x)//更新懒标签 {    t[2*x].sum+=((t[2*x].r-t[2*x].l+1)*t[x].lazy)%mo;    t[2*x+1].sum+=((t[2*x+1].r-t[2*x+1].l+1)*t[x].lazy)%mo;    t[2*x].lazy+=t[x].lazy;t[2*x].lazy%=mo;    t[2*x+1].lazy+=t[x].lazy;t[2*x+1].lazy%=mo;    t[x].lazy=0;}void change(int x,int l,int r,int z)//改变值 {    if(t[x].l==l&&t[x].r==r)    {        t[x].sum+=(t[x].r-t[x].l+1)*z;        t[x].lazy+=z;        return ;    }    if(t[x].lazy) update(x);    int mid=(t[x].l+t[x].r)>>1;    if(r<=mid) change(2*x,l,r,z);    else if(l>mid) change(2*x+1,l,r,z);    else    {        change(2*x,l,mid,z);        change(2*x+1,mid+1,r,z);    }    t[x].sum=(t[2*x].sum+t[2*x+1].sum)%mo;}int query(int x,int l,int r)//查询区间和 {    if(t[x].l==l&&t[x].r==r)    {        return t[x].sum;    }    if(t[x].lazy) update(x);    int mid=(t[x].l+t[x].r)>>1;    if(r<=mid) return query(2*x,l,r);    else if(l>mid) return query(2*x+1,l,r);    else     {        return query(2*x,l,mid)+query(2*x+1,mid+1,r);    }}//上面是线段树 void dfs1(int u,int fa){    f[u]=fa;//记录u节点的父亲     siz[u]=1;//子树大小，包括他自己     dep[u]=dep[fa]+1;//深度     for(int p=last[u];p;p=pre[p])    {        int v=other[p];        if(v==fa) continue;        dfs1(v,u);        siz[u]+=siz[v];        if(siz[v]>siz[son[u]]) son[u]=v;//记录重儿子         }}void dfs2(int u,int tp){    id[u]=++cnt;//重新编号     top[u]=tp;//这个点所在链的顶端     b[cnt]=a[u];//新编号赋值    if(!son[u]) return ;//no son    dfs2(son[u],tp);    for(int p=last[u];p;p=pre[p])    {        int v=other[p];        if(v==son[u]||v==f[u]) continue;        dfs2(v,v);//对于每一个轻儿子都有一条从它自己开始的链     }    }void tchange(int x,int y,int z){    z%=mo;    while(top[x]!=top[y])//如果不在一条链上     {        if(dep[top[x]]
        
         dep[y]) swap(x,y);//找到深度浅的那个     change(1,id[x],id[y],z);//最后一条链加z }int tcha(int x,int y){    int ans=0;    while(top[x]!=top[y])    {        if(dep[top[x]]
         
          dep[y]) swap(x,y);    ans+=query(1,id[x],id[y]);    ans%=mo;    return ans;}void changeson(int x,int z){    change(1,id[x],id[x]+siz[x]-1,z);//新编节点中每个节点和儿子们是连续的多么重要 }int chason(int x){    return query(1,id[x],id[x]+siz[x]-1);}int main(){    scanf("%d%d%d%d",&n,&m,&s,&mo);    for(int i=1;i<=n;i++)    {        scanf("%d",&a[i]);    }    for(int i=1;i
         
        
       
      
     

 

刚学会，理解还是不太到位，欢迎指正。

 

 

 

 

 

 

 

温馨提示（放在最后坑你们）：每个加减计算都要取模。。。。。。