差分、二维差分、树上差分

差分

概念

对于一个数组arr，如果要将长为m的区间内的所有元素增加 x，常规的做法是遍历进行操作，复杂度为O(m)，但如果这样的操作不是1次而是n次，则复杂度会变为O(mn)。如果要优化时间复杂度，可以借助差分数组进行：

例如，数组arr长为n，定义一个长为n+1的差分数组diff。将区间arr[l: r]中的元素增加x，等效于将diff[l]加上x，将diff[r]减去x后求前缀和。

题目

代码

public boolean carPooling(int[][] trips, int capacity) {
    int[] diff = new int[1001];
    for(int[] trip: trips){
        diff[trip[1]] += trip[0];
        diff[trip[2]] -= trip[0];
    }
    if(diff[0] > capacity) return false;
    for(int i = 1;i <= 1000;++i){
        diff[i] += diff[i-1];
        if(diff[i] > capacity) return false;
    }
    return true;
}

二维差分

概念

下面推广至二维场景，即在一个二维数组中，将一个子矩阵的元素值全部增加某个值。与一维差分借助一维前缀和类似，二维差分需要借助二维前缀和的方法。假设要将mat中的一个子矩阵sub（四个边界用up、down、left、right表示）全部增加x，具体流程如下：

首先定义一个 m+1 * n +1 的二维差分数组diff
对于每次操作，将diff[up][left]与diff[down+1][right+1]增加 x，diff[up][right+1]与diff[down+1][left]减少 x
求二维前缀和，忽略右端/下端的列/行，结果即为操作后的mat矩阵

题目

2536. 子矩阵元素加 1 - 力扣（LeetCode）

代码

public int[][] rangeAddQueries(int n, int[][] queries) {
    int[][] diff = new int[n+1][n+1];
    for(int[] q: queries){
        diff[q[0]][q[1]]++;
        diff[q[2]+1][q[3]+1]++;
        diff[q[0]][q[3]+1]--;
        diff[q[2]+1][q[1]]--;
    }
    for(int i = 0;i < n;++i) for(int j = 1;j < n;++j) diff[i][j] += diff[i][j-1];
    for(int i = 1;i < n;++i) for(int j = 0;j < n;++j) diff[i][j] += diff[i-1][j];
    int[][] ans = new int[n][n];
    for(int i = 0;i < n;++i){
        for(int j = 0;j < n;++j){
            ans[i][j] = diff[i][j];
        }
    }
    return ans;
}

树上差分

概念

差分思想同样可以用在树上，考虑场景：把树上的一条路径上的节点计数值全部加1。从起点 x 到终点 y 的路径可以视作从 x 向上到某个点「拐弯」，再向下到达 y。

这个拐弯的点是 x 和 y 的 lca（最近公共祖先），因此需要配合LCA问题求解方法。注意拐弯的点也可能就是 x 或 y 本身。

设路径为 x−z−lca−y，其中 z 是 lca 往 x 方向的儿子。这条路径可以拆分成 x−z 和 y−lca 两段。

把路径上的点的计数加一，转换成对差分数组 diff 的两个数的更新。规定把下面的点加一，把上面的点减一：

对于 x−z，把 diff[x] 加一，diff[lca] 减一。注意，如果 x 就是 lca，那么 z 是不存在的，而差分操作刚好对 diff[x] 加一再减一，没有变化。所以我们无需特判 x 就是 lca 的情况。
对于 y−lca，把 diff[y] 加一，diff[father[lca]] 减一，其中 father[lca] 表示 lca 的父节点。

完成差分数组的求解后，DFS这棵树，在递归过程中自底向上累加即可得到最终的计数。