序列/树上差分小结 By cellur925

首先我们需要注意一下的是，差分比较适用于修改比较多而查询比较少的情况。

一、序列上差分

借教室这是一道二分答案，在check函数中用到差分技巧的一道题，譬如说我们要把一个序列中[l,r]区间都加上一个权值，我们可以把在 l 处加上这个值，在r+1处减去这个值，再对记录权值的数组求前缀和，那么我们就可以得到这个真正的权值数组。

题解在链接里，代码就不放了=w=。

二、树上差分

树上差分可以分为在点权上的情况和在边权上的情况。

1：　　　　点权：

比如在树上把从u到v的路径的某个权值都加上一个数，设这个权值数组val，那么我们需要在val[u]，val[v]上加上这个值，并在val[lca(u,v)]上减去这个值，并在val[f[lca(u,v][0]]上减去这个值。

理论如斯。

这个算法就经常用于统计树上路径某点/某边的经过次数。

例题1 [USACO15DEC]最大流Max Flow（不是网络流题目啦==）

给出若干路径，求被经过此处最多的点的经过次数。

Sol：树上倍增求LCA+树上差分记录+最后O（n）扫一遍更新。

总复杂度O（nlogn预处理+klogn求LCA+n更新）

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #define maxn 500900

 using namespace std;

 int n,k,t,ans,tot;

 int head[maxn],d[maxn],val[maxn],f[maxn][];

 struct node{

     int to,next;

 }edge[maxn*];

 void add(int x,int y)

 {

     edge[++tot].next=head[x];

     head[x]=tot;

     edge[tot].to=y;

 }

 void init_LCA()

 {

     queue<int>q;

     q.push();

     d[]=;

     while(!q.empty())

     {

         int u=q.front();

         q.pop();

         for(int i=head[u];i;i=edge[i].next)

         {

             int v=edge[i].to;

             if(d[v]) continue;

             d[v]=d[u]+;

             f[v][]=u;

             for(int j=;j<=t;j++)

                 f[v][j]=f[f[v][j-]][j-];

             q.push(v);

         }

     }

 }

 int LCA(int x,int y)

 {

     if(d[x]>d[y]) swap(x,y);

     for(int i=t;i>=;i--)

         if(d[f[y][i]]>=d[x]) y=f[y][i];

     if(x==y) return x;

     for(int i=t;i>=;i--)

         if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];

     return f[x][];

 }

 void review(int u,int fa)

 {

     for(int i=head[u];i;i=edge[i].next)

     {

         int v=edge[i].to;

         if(v==fa) continue;

         review(v,u);

         val[u]+=val[v];

     }

     ans=max(ans,val[u]);

 }

 int main()

 {

     scanf("%d%d",&n,&k);

     t=log2(n)+;

     for(int i=;i<=n-;i++)

     {

         int x=,y=;

         scanf("%d%d",&x,&y);

         add(x,y),add(y,x);

     }

     init_LCA();

     while(k--)

     {

         int x=,y=;

         scanf("%d%d",&x,&y);

         int fa=LCA(x,y);

 //        printf("%d\n",fa);

         val[x]++;val[y]++;

         val[fa]--;val[f[fa][]]--;

     }

     review(,);

     printf("%d",ans);

     return ;

 }

例题2 [JLOI2014]松鼠的新家

也是求点经过次数的=w=，稍有变动，需要在最后从第2个到达点到最后一个到达点的权值都减。（题意使然）

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #define maxn 300090

 using namespace std;

 int n,tot,t;

 int seq[maxn],head[maxn],val[maxn],d[maxn],f[maxn][];

 struct node{

     int to,next;

 }edge[maxn*];

 void add(int x,int y)

 {

     edge[++tot].to=y;

     edge[tot].next=head[x];

     head[x]=tot;

 }

 void LCA_prework()

 {

     queue<int>q;

     q.push(),d[]=;

     while(!q.empty())

     {

         int u=q.front();q.pop();

         for(int i=head[u];i;i=edge[i].next)

         {

             int v=edge[i].to;

             if(d[v]) continue;

             d[v]=d[u]+;

             f[v][]=u;

             for(int j=;j<=t;j++)

                 f[v][j]=f[f[v][j-]][j-];

             q.push(v);

         }

     }

 }

 int LCA(int x,int y)

 {

     if(d[x]>d[y]) swap(x,y);

     for(int i=t;i>=;i--)

         if(d[f[y][i]]>=d[x]) y=f[y][i];

     if(x==y) return x;

     for(int i=t;i>=;i--)

         if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];

     return f[x][];

 }

 void review(int u,int fa)

 {

     for(int i=head[u];i;i=edge[i].next)

     {

         int v=edge[i].to;

         if(v==fa) continue;

         review(v,u);

         val[u]+=val[v];

     }

 }

 int main()

 {

     scanf("%d",&n);

     t=log2(n)+;

     for(int i=;i<=n;i++) scanf("%d",&seq[i]);

     for(int i=;i<=n-;i++)

     {

         int x=,y=;

         scanf("%d%d",&x,&y);

         add(x,y),add(y,x);

     }

     LCA_prework();

     for(int i=;i<=n-;i++)

     {

         int fa=LCA(seq[i],seq[i+]);

         val[seq[i]]++;val[seq[i+]]++;

         val[fa]--;val[f[fa][]]--;

     }

     review(,);

     for(int i=;i<=n;i++) val[seq[i]]--;

     for(int i=;i<=n;i++) printf("%d\n",val[i]);

     return ;

 }

（话说省选出板子题真的好么==）

2：　　　　边权：

给你一棵树，有n次修改操作，每次把u..v的路径权值加x，最后问从x..y的路径权值和。

例如有一次操作是把红点（u）到绿点（v）之间的路径全部加x。那么我就标记dlt[u]+=x,dlt[v]+=x。然后我们要在lca(u,v)处标记dlt[lca(u,v)]-=2x。这样就使得加x的效果只局限在u..v，不会向lca(u,v)的爸爸蔓延。

上面的话引用自@Sagittariusdalao。

例题：NOIp2015运输计划

val[x]就是x与它的父节点之间的“树边”被覆盖的次数

链接中有详细的题解==

巴特西

序列/树上差分小结 By cellur925

一、序列上差分

二、树上差分

小结：树上差分和树上倍增还是比较实用的，也比较灵活，需要加强举一反三能力==

最新文章

热门文章