差分

• 对于数组a：$a[1], a[2], …, a[n]$，其对应的差分数组为数组b：$b[i], b[2], …, b[n]$（数组a，b的第一项都为0，便于计算前缀和）
• 其中$b[1] = a[1]-a[0], b[2] = a[2]-a[1], …, b[n] = a[n]-a[n-1]$
• 我们可以发现$a[i] = b[1] + b[2] + b[3] + … + b[n]$
• 即a为b求前缀和的结果，b为a的差分，前缀和与差分互为逆运算
• 构造差分数组的两个步骤（对于a的[l,r]区间的每个数都加上c）：
  1.$b[l]+c$：求前缀和恢复原数组a时，下标l以后的每个数都会加上c
  2.$b[r+1]-c$：求前缀和恢复原数组a时，下标r+1以后的每个数不需要加上c，需要减c来抵消

差分的作用

• 差分可以在$O(1)$的时间内对一段连续的区间进行数据的更新，例如把某个连续的区间加上一个数，或者减去一个数。我们只需要对差分数组进行操作，最后对差分数组求前缀和，用$O(n)$的时间得出更新后的原数组

模板题

• 链接：差分

写法1：朴素写法

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] a = new int[n+1];
        for(int i = 1; i <= n; i++) a[i] = sc.nextInt();
        // r最大到n，r+1可能达到n+1，所以数组大小开到n+2
        int[] b = new int[n+2];
        for(int i = 1; i <= n; i++) b[i] = a[i] - a[i-1];
        for(int i = 0; i < m; i++){
            int l = sc.nextInt(), r = sc.nextInt(), c = sc.nextInt();
            b[l] += c;
            b[r+1] -= c;
        }
        int[] s = new int[n+1];
        for(int i = 1; i <= n; i++) {
            s[i] = s[i-1] + b[i];
            System.out.print(s[i] + " ");
        }
    }
}

写法2：直接对差分数组进行操作

• 我们可以发现，可以不用通过原数组构造差分数组，$a[i] = c$等价于在区间[1,1]中添加一个数值为c的数，即$diff[i] = diff[i] + c$ 和 $diff[i+1] = diff[i+1] - c$

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] diff = new int[n+2];
        for(int i = 1; i <= n; i++) {
            int c = sc.nextInt();
            diff[i] += c;
            diff[i+1] -= c;
        }

        for(int i = 0; i < m; i++){
            int l = sc.nextInt(), r = sc.nextInt(), c = sc.nextInt();
            diff[l] += c;
            diff[r+1] -= c;
        }
        int[] s = new int[n+1];
        for(int i = 1; i <= n; i++) {
            diff[i] = diff[i-1] + diff[i];
            System.out.print(diff[i] + " ");
        }
    }
}

例题1.使数组互补的最少操作次数

• 链接：LeetCode1674.使数组互补的最少操作次数

  这是217周赛的第三题，比赛的时候完全被吊打，没看出来这题和差分有啥关系，果然学了模板还需要实际问题来训练啊

解法1.暴力枚举所有可能的目标值

• 根据题意，发现目标值只可能在[2, 2*limit]之间，可以预处理一个数组，来记录每个目标值所对应的操作次数，最后取最小值就是答案了，但是时间复杂度达到了$O(n * limit)$，最大可达到$1^{10}$，显然是超时的，我们想办法优化这个算法
• j的范围可以被分成几个区间：$[2, min(v,w)], [min(v,w)+1, max(v,w)+limit], [max(v,w)+limit+1, 2*limit], [v+w, v+w]$，分别需要操作2次，操作1次，操作2次，操作0次，且$v+w$为操作1次区间上的一个点，通过区间范围可以统计目标值为$j$所需要的操作次数。

class Solution {
    public int minMoves(int[] nums, int limit) {
        int[] a = new int[2*limit+1];//a[i]表示目标值为i的操作次数
        // 目标值一定在[2, 2*limit]中
        int n = nums.length;
        for(int i = 0; i < n/2; i++){
            int v = nums[i], w = nums[n-i-1];
            for(int j = 2; j <= 2*limit; j++){
                if(v + w == j){
                    continue;
                }else if(j <= Math.min(v,w) || j > Math.max(v,w) + limit){
                    a[j] += 2;
                }else{
                    a[j]++;
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for(int i = 2; i <= 2*limit; i++){
            res = Math.min(res, a[i]);
        }
        return res;
    }
}

解法2.差分数组

• 暴力做法，每次循环2*limit次来统计a[j]的值，而$j$是一段[2, 2*limit]的连续区间，我们可以通过差分数组对区间查询做一个优化，去掉内层循环，把时间复杂度压缩到$O(n+limit)$

class Solution {
    public int minMoves(int[] nums, int limit) {
        int[] diff = new int[2*limit+2];
        int n = nums.length;
        for(int i = 0; i < n/2; i++){
            int v = nums[i], w = nums[n-i-1];
            // [v+w, v+w]上不用操作, min(v,w) + 1 <= v+w <= max(v,w)+limit, 这个点在操作一次的区间上
            // [2, min(v,w)], (max(v,w)+limit, 2*limit]上操作两次
            // [min(v,w)+1, max(v,w)+limit]上操作一次
            int l = Math.min(v,w)+1, r = Math.max(v,w)+limit;
            diff[l] += 1;
            diff[r+1] -= 1;

            l = 2; r = Math.min(v,w);
            diff[l] += 2;
            diff[r+1] -= 2;

            l = Math.max(v,w)+limit+1; r = 2*limit;
            diff[l] += 2;
            diff[r+1] -= 2;

            l = v+w; r = l;
            diff[l] += -1;
            diff[r+1] -= -1;
        }
        int res = Integer.MAX_VALUE;
        int sum = 0;
        for(int i = 2; i <= 2*limit; i++){
            diff[i] = diff[i-1] + diff[i];
            res = Math.min(res, diff[i]);
        }
        return res;
    }
}