前缀和&差分

· · 算法·理论

前缀和

定义

前缀和可以简单理解为 \lceil 数列的前 n 项的和 \rfloor，是一种重要的预处理方式，能大大降低查询的时间复杂度。

例题

有 n 个的正整数放到数组 a 里，现在要求一个新的数组 b，新数组的第 i 个数 b_i 是原数组 a 第 1 到第 i 个数的和。

输入

5
1 2 3 4 5

输出

1 3 6 10 15

解题思路

递推：B[1]=A[1]，对于 i\ge 2 则 B[i]=b[i-1]+A[i]。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N],b[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    // 前缀和数组的第一项和原数组的第一项是相等的。
    b[1] = a[1];
    for (int i = 2; i <= n; i++) {
        // 前缀和数组的第 i 项 = 原数组的 0 到 i-1 项的和 + 原数组的第 i 项。
        b[i] = b[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        cout << b[i] << " ";
    }
    return 0;
}

高维前缀和

常见的多维前缀和的求解方法有两种。

树上前缀和

设 sum_i 表示结点 i 到根节点的权值总和。 然后：

差分

解释

差分是一种和前缀和相对的策略，可以当做是求和的逆运算。

这种策略的定义是令 b_i = \begin{cases} a_i - a_{i-1} & i \in [2,n] \\ a_1 & i=1 \end{cases}

性质

它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。

树上差分

树上差分可以理解为对树上的某一段路径进行差分操作，这里的路径可以类比一维数组的区间进行理解。例如在对树上的一些路径进行频繁操作，并且询问某条边或者某个点在经过操作后的值的时候，就可以运用树上差分思想了。

树上差分通常会结合 最近公共祖先 来进行考察。树上差分又分为 点差分 与 边差分，在实现上会稍有不同。

点差分

举例：对树上的一些路径 \delta(s_1,t_1), \delta(s_2,t_2), \delta(s_3,t_3)\dots 进行访问，问一条路径 \delta(s,t) 上的点被访问的次数。

对于一次 \delta(s,t) 的访问，需要找到 s 与 t 的公共祖先，然后对这条路径上的点进行访问（点的权值加 1），若采用 DFS 算法对每个点进行访问，由于有太多的路径需要访问，时间上承受不了。这里进行差分操作：

d_s\gets d_s+1 d_{lca}\gets d_{lca}-1 d_t\gets d_t+1 d_{father(lca)}\gets d_{father(lca)}-1

其中 father(x) 表示 x 的父亲结点，d_i 为点权 a_i 的差分数组。

可以认为公式中的前两条是对蓝色方框内的路径进行操作，后两条是对红色方框内的路径进行操作。不妨令 \textit{lca} 左侧的直系子节点为 \textit{left}。那么有 d_{\textit{lca}}-1=a_{\textit{lca}}-(a_{\textit{left}}+1)，d_{f(\textit{lca})}-1=a_{f(\textit{lca})}-(a_{\textit{lca}}+1)。可以发现实际上点差分的操作和上文一维数组的差分操作是类似的。

边差分

若是对路径中的边进行访问，就需要采用边差分策略了，使用以下公式：

d_s\gets d_s+1 d_t\gets d_t+1 d_{lca}\gets d_{lca}-2

由于在边上直接进行差分比较困难，所以将本来应当累加到红色边上的值向下移动到附近的点里，那么操作起来也就方便了。对于公式，有了点差分的理解基础后也不难推导，同样是对两段区间进行差分。

例题

洛谷P3128

解题思路

需要统计每个点经过了多少次，那么就用树上差分将每一次的路径上的点加一，可以很快得到每个点经过的次数。这里采用倍增法计算 LCA，最后对 DFS 遍历整棵树，在回溯时对差分数组求和就能求得答案了。

参考代码

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
const int N=5e4+10,L=20;
int n,m,fa[N][L],dep[N],cnt[N],ma,k,pre[N],lg[N];

struct node{
    int to;
    int next;
}a[2*N];

void add(int u,int v){//建边
    a[++k]={v,pre[u]};
    pre[u]=k;
    return ;
}

void init(){//预处理log2
    lg[1]=0;
    for(int i=2;i<=n;i++)
        lg[i]=lg[i>>1]+1;
    return ;
}

void dfs(int x,int fath){//求深度、父亲结点
    dep[x]=dep[fath]+1;
    fa[x][0]=fath;
    for(int i=pre[x];i;i=a[i].next){
        int to=a[i].to;
        if(to!=fath){
            dfs(to,x);
        }
    }
    return ;
}

int lca(int u,int v){//求lca
    if(dep[u]<dep[v]) swap(u,v);
    while(dep[u]!=dep[v]){
        u=fa[u][lg[dep[u]-dep[v]]];
    } 
    if(u==v) return u;
    for(int i=L-1;i>=0;i--){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}

void dfs2(int x,int fath){
    for(int i=pre[x];i;i=a[i].next){
        int to=a[i].to;
        if(to!=fath){
            dfs2(to,x);
            cnt[x]+=cnt[to];//差分后前缀和操作
        }
    }
    ma=max(ma,cnt[x]);
    return ;
}

signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }

    init();

    dfs(1,0);

    //倍增法求lca
    for(int j=1;j<L;j++){
        for(int i=1;i<=n;i++){
            fa[i][j]=fa[fa[i][j-1]][j-1];
        }
    }

    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        int lc=lca(x,y);
        //差分
        cnt[x]++;
        cnt[y]++;
        cnt[lc]--;
        cnt[fa[lc][0]]--;
    }

    dfs2(1,0);

    printf("%d",ma);
    return 0;
}