差分与树上差分

算法简介

差分用于解决多次区间加减法，少量单点查询的问题。
若有多次区间加减法、少量单点查询，暴力不行，线段树是通法，但不如今天要学的差分！

普通差分

普通差分就解决序列上的问题。

思想、定义与操作

1、对一个序列\(a\)，设\(b[i]=a[i]-a[i-1](a[0]=0)\)，则\(a[i]=\sum_{j=1}^{i} {b[j]}\)；
2、对于\(a[i]到a[j]\)加上\(k\)的操作，\(b[i]+=k，b[j+1]-=k\)；
3、查询时，用上面公式。
时间复杂度：修改一次是\(O(1)\)，查询是\(O(N)\)。

这就是普通差分，简单得很。它一般搭配别的数据结构使用，比如树状数组什么的。

树上差分

如果是在树上对一条路径上点或边加减，怎么办？
固然可以树链剖分，但脑袋会炸，时间复杂度\(O(n\log_{2}^{2}n)\)也不利于得高分。
所以树上差分是更好的选择。

点的差分

这是对点进行操作。

思想、定义与操作

1、\(b[i]\)表示\(i\)到根节点的路径增加的值；
2、当\(u\)到\(v\)要加\(k\)时，\(b[u]、b[v]+=k\)；
3、此时\(lca(u,v)多加了一个k，其所有父节点多加了2个k\)，所以\(b[lca(u,v)]-=k,b[fa[lca(u,v)]]-=k\)；
4、查询时\(dfs\)一次，每个点的值为原本的值加上到根节点路径上\(b\)的和。
时间复杂度：修改一次是\(O(1)\)，查询是\(O(N)\)。

代码

1、洛谷P3128 最大流
这就是模板。

#include<bits/stdc++.h>
using namespace std;
int n,a[50001],b[50001],head[50001],dep[50001],sz[50001],num;
int fa[50001],sn[50001],top[50001],id[50001],cnt,m,maxn=-2147483647;
struct E{
    int next,to;
}e[100001];
inline int Read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
          f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void Write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
      Write(x/10);
    putchar(x%10+'0');
}
void Adde(int u,int v)
{
    e[++num].next=head[u];
    e[num].to=v;
    head[u]=num;
}
int Dfs1(int u,int f)
{
    fa[u]=f;
    dep[u]=dep[f]+1;
    sz[u]=1;
    int maxs=-1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==f)
          continue;
        sz[u]+=Dfs1(v,u);
        if(sz[v]>maxs)
        {
            maxs=sz[v];
            sn[u]=v;
        }
    }
    return sz[u];
}
void Dfs2(int u,int tp)
{
    id[u]=++cnt;
    top[u]=tp;
    if(!sn[u])
      return;
    Dfs2(sn[u],tp);
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(!id[v])
          Dfs2(v,v);
    }
}
int Lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
          swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])
      return x;
    return y;
}
/*int Queryx(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
          swap(x,y);
        ans+=Query(1,id[top[x]],id[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
      swap(x,y);
    ans+=Query(1,id[x],id[y]);
    return ans;
}
*/
void Dfs(int u,int f)
{
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==f)
          continue;
        Dfs(v,u);
        b[u]+=b[v];

    }
    maxn=max(maxn,b[u]);
}
int main()
{
    n=Read(),m=Read();
    int u,v,lca;
    for(register int i=1;i<n;++i)
    {
        u=Read(),v=Read();
        Adde(u,v);
        Adde(v,u);
    }
    Dfs1(1,0);
    Dfs2(1,1);
    for(int i=1;i<=m;++i)
    {
        u=Read(),v=Read();
        lca=Lca(u,v);
        b[u]++;
        b[v]++;
        b[lca]--;
        b[fa[lca]]--;
    }
    Dfs(1,0);
    Write(maxn);
    return 0;
}

边的差分

不会，学了再填坑。