树上差分-白红宇

树上差分

阅读量：3951 次

发布时间：2019-05-24

本文共 3377 字，大约阅读时间需要 11 分钟。

差分

差分是前缀和的逆运算。 $d_{1...n}$ 是差分数组， $a_{1...n}$ 是原数组。关系如下式。

d_i=a_i-a_{i-1}

则通过

d_{1...n}

数组求

a_i

,为求

d_{1...n}

数组的前缀和。

a_i = \sum_{j=1}^id_j

通过

d_{1...n}

数组求前缀和为

sum_i=\sum_{i=1}^n{\sum_{j=1}^id_i}=\sum_{i=1}^n(n-i+1)d_i

应用

求第一个不能减的区间。

二分借教室操作数，用差分数组

O (n)

借教室，总时间复杂度为

O(n\log m)

#include 
   
    #define debug(__x) cout<<#__x<<"="<<__x<
    
      range;ll a[maxn];    // 差分数组int n,m;void sub(int l,int r){
     // 借教室操作    for(int i=l;i<=r;++i){
           a[range[i].s]-=range[i].d;        a[range[i].t+1]+=range[i].d;    }}void add(int l,int r){
       // 撤销借教室操作    for(int i=l;i<=r;++i){
           a[range[i].s]+=range[i].d;        a[range[i].t+1]-=range[i].d;    }}bool judge(){
     // 判断是否有一天教室数不够借    int now = 0;    for(int i=1;i<=n;++i){
           now += a[i];        if(now<0)return false;    }    return true;}int main(){
       cin.tie(0),cout.tie(0);    ios::sync_with_stdio(false);    cin>>n>>m;    for(int now,last=0,i=1;i<=n;++i){
           cin>>now;        a[i] = now - last;        last = now;    }    for(int d,s,t,i=0;i
     
      >d>>s>>t;        range.emplace_back(d,s,t);    }    sub(0,m-1);    if(judge()){
           cout<<0<
      
       >1;        sub(l,mid);       // debug(l);debug(r);        if(judge()){
               l = mid + 1;        }else{
               r = mid;            add(l,mid);        }    }    cout<
       
        <

树上差分

就是在树上进行差分操作，实现功能与差分一样，可以 $O (1)$ 实现区间修改。分为点差分和边差分。

点差分

cnt[u]+=x可理解为u到树跟的路径上所有节点的权重加x。在把(u,v)路径上的点权加x的操作如下。

cnt[u] += x;cnt[v] += x;cnt[lca] -= x;cnt[fa[lca]] -= x;

用差分数组求点权

val[u]=\sum_{v\in SubTree_{root=u}}cnt[v]

边差分

把每个点连到它的父节点的边权放在该点上。原理和点分治一样。在把(u,v)路径上的边权加x的操作如下。

cnt[u] += x;cnt[v] += x;cnt[lca] -= 2*x;

模板

在一棵树上，在给定点对的路径上的点权加1。求最大点权。树上差分最适合修改多查询少的题。这题只用1次查询。

#include 
   
    #define debug(__x) cout<<#__x<<"="<<__x<
    
      G[maxn];int f[maxn][15];int cnt[maxn];int dep[maxn];int ans=0;void dfs(int u,int fa){
       f[u][0] = fa;    dep[u] = dep[fa] + 1;    for(int i=1;i<15;++i)        f[u][i] = f[f[u][i-1]][i-1];    for(int son : G[u]){
           if(son == fa)continue;        dfs(son,u);    }}int lca(int x,int y){
       if(dep[x] < dep[y]) swap(x,y);    int t = dep[x] - dep[y];    for(int i=0;i<15;++i)        if(t&(1<
     
      =0;--i){
           if(f[x][i]!=f[y][i]){
               x=f[x][i];            y=f[y][i];        }    }    return f[x][0];}void sum(int u,int fa){
       for(int son : G[u]){
           if(son == fa)continue;        sum(son,u);        cnt[u] += cnt[son];    }}int main(){
       cin.tie(0),cout.tie(0);    ios::sync_with_stdio(false);    int n,k;    cin>>n>>k;    for(int u,v,i=1;i
      
       >u>>v;        G[u].push_back(v);        G[v].push_back(u);    }    dfs(1,0);    while(k--){
           int u,v;        cin>>u>>v;        int ac = lca(u,v);        ++cnt[u];        ++cnt[v];        --cnt[ac];        --cnt[f[ac][0]];    }    sum(1,0);   // 把差分数组转换为每个点的点权    for(int i=1;i<=n;++i){
           if(cnt[i]>ans) ans = cnt[i];    }    cout<
       
        <