【LuoguP3038/[USACO11DEC]牧草种植Grass Planting】树链剖分+树状数组【树状数组的区间修改与区间查询】

模拟题，可以用树链剖分+线段树维护。

但是学了一个厉害的。。树状数组的区间修改与区间查询。。

分割线里面的是转载的：

--------------------------------------------------------------------------------

[ 3 ]  上面都不是重点……重点是树状数组的区间修改+区间查询 这个很好玩 其实也挺简单

首先依旧是引入delta数组 delta[i]表示区间 [i, n] 的共同增量 于是修改区间 [l, r] 时修改 delta[l] 和 delta[r + 1] 即可（就是差分的思路）

查询的时候是查询区间 [l, r] 的和 即sum[r] - sum[l - 1] 所以现在的问题是求sum[i]

 sum[i] = a[]+...+a[i] + delta[]*i + delta[]*(i - ) + delta[]*(i - )+...+delta[i]*   // a[i]为原始数组

        = sigma( a[x] ) + sigma( delta[x]  *  (i +  - x) )

        = sigma( a[x] ) + (i + ) * sigma( delta[x] ) - sigma( delta[x] * x ) 

 

其中 sigma( a[x] ) 是可以预处理出来的 于是只需要维护 delta[x] 与 delta[x] * x 的前缀和（作为两个树状数组就可以了）

为了试验这个方法我专门去找了之前写线段树挂了好久的例题 = = codevs1082 线段树练习3

然后交树状数组的代码是 324ms 内存5M过了 线段树是1027ms 13M 如果去掉读入优化的话代码会更短。

--------------------------------------------------------------------------------------------------------------------------

转自：http://blog.csdn.net/qq_21841245/article/details/43956633

很好。。这题本机测系统暴栈了。。交上去才A。。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<ctime>

 #include<queue>

 using namespace std;

 const int N=*,S=,D=;

 struct node{

     int x,y,next;

 }a[*N];

 struct trnode{

     int l,r,lc,rc,d;

 }t[*N];

 int n,m,len,num,first[N],dep[N],f[N][S],tot[N],zs[N],dfn[N],top[N],c0[N],c1[N],delta[N];

 char s[];

 void add(int x,int d)

 {

     for(int i=x;i<=n;i+=(i&(-i))) c0[i]+=d,c1[i]+=d*x;

 }

 int getsum(int x)

 {

     int a0=,a1=;

     for(int i=x;i>=;i-=(i&(-i))) a0+=c0[i],a1+=c1[i];

     return a0*(x+)-a1;

 }

 void ins(int x,int y)

 {

     a[++len].x=x;a[len].y=y;

     a[len].next=first[x];first[x]=len;

 }

 void dfs(int x,int fa)

 {

     dep[x]=dep[fa]+;

     f[x][]=fa;

     tot[x]=;

     zs[x]=;

     for(int i=first[x];i;i=a[i].next)

     {

         int y=a[i].y;

         if(y==fa) continue;

         dfs(y,x);

         tot[x]+=tot[y];

         if(zs[x]== || tot[y]>tot[zs[x]]) zs[x]=y;

     }

 }

 void find_top(int x,int fa)

 {

     dfn[x]=++num;

     if(zs[x])

     {

         top[zs[x]]=top[x];

         find_top(zs[x],x);

     }

     for(int i=first[x];i;i=a[i].next)

     {

         int y=a[i].y;

         if(y==fa || y==zs[x]) continue;

         top[y]=y;

         find_top(y,x);

     }

 }

 int solve(int x,int y,int tmp)

 {

     int tx=top[x],ty=top[y],ans=;

     while(tx!=ty)

     {

         if(dep[tx]<dep[ty]) swap(x,y),swap(tx,ty);

         if(tmp==)

         {

             add(dfn[tx],);

             add(dfn[x]+,-);

         }

         else ans+=getsum(dfn[x])-getsum(dfn[tx]-);

         x=f[top[x]][];tx=top[x];

     }

     if(x==y) return ans;

     else

     {

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

         if(tmp==)

         {

             add(dfn[y]+,);

             add(dfn[x]+,-);

         }

         else ans+=getsum(dfn[x])-getsum(dfn[y]);

         return ans;

     }

 }

 void lca_init()

 {

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

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

             f[i][j]=f[f[i][j-]][j-];

 }

 int lca_query(int x,int y)

 {

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

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

     {

         if(f[x][i]==) continue;

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

     }

     if(x==y) return x;

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

     {

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

     }

     return f[x][];

 }

 int main()

 {

     freopen("a.in","r",stdin);

     // freopen("a.out","w",stdout);

     // freopen("grassplant.in","r",stdin);

     // freopen("grassplant.out","w",stdout);

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

     int x,y,z;len=;num=;

     memset(first,,sizeof(first));

     memset(f,,sizeof(f));

     memset(c0,,sizeof(c0));

     memset(c1,,sizeof(c1));

     memset(dep,,sizeof(dep));

     memset(tot,,sizeof(tot));

     memset(zs,,sizeof(zs));

     memset(dfn,,sizeof(dfn));

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

     {

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

         ins(x,y);

         ins(y,x);

     }

     dfs(,);

     top[]=;find_top(,);

     // for(int i=1;i<=n;i++)

     // {

         // printf("i = %d  dep = %d  zs = %d  tot = %d  dfn = %d  top = %d\n",i,dep[i],zs[i],tot[i],dfn[i],top[i]);

     // }

     lca_init();

     for(int i=;i<=m;i++)

     {

         scanf("%s",s);

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

         if(s[]=='P')

         {

             z=lca_query(x,y);

             solve(x,z,);

             solve(y,z,);

         }

         else

         {

             printf("%d\n",solve(x,y,));

         }

     }

     return ;

 }

【LuoguP3038/[USACO11DEC]牧草种植Grass Planting】树链剖分+树状数组【树状数组的区间修改与区间查询】的相关教程结束。