差分数组

差分数组通常是指一个数组，其中每个元素是原数组中对应元素与前一个元素的差。这种数组在处理序列数据时非常有用，尤其是在需要计算连续项之间的变化或者进行数据压缩时。
定理解释：
差分数组的一个核心定理是，给定一个差分数组，可以唯一地重建原始数组。这意味着，如果你有一个差分数组，你可以通过累加的方式恢复原始数组。这个定理的成立基于以下几个步骤：
差分数组的构建：假设有一个原始数组 A[1…n]，我们可以构建一个差分数组 D[1…n]，其中 D[i] = A[i] - A[i-1]，对于 i = 2, 3, …, n，且 D[1] = A[1]（或者可以选择 D[1] = 0，如果 A[1] 是相对于某个已知的起始值）。
原始数组的重建：给定差分数组 D[1…n]，我们可以重建原始数组 A[1…n]，方法是从 A[1] = D[1] 开始，然后对于每个 i（2 ≤ i ≤ n），计算 A[i] = A[i-1] + D[i]。
这个定理的证明是直接的，因为你可以通过反向操作来验证重建的数组是否与原始数组相同。从 A[1] 开始，使用差分数组中的每个差值逐步累加，最终得到的 A[n] 应该与原始数组的最后一个元素相同。
应用场景：
1.数据压缩：减少存储空间，特别是在数据变化不大时。
2.快速求和：快速计算数组中任意一段区间的和。
3.更新和查询：在数组中快速更新值并查询特定统计信息。
4.游戏开发：处理游戏中角色位置等动态变化的数据。
5.信号处理：在音频或视频编辑中表示信号的变化。

下面解释了差分数组进行区间修改图示方便大家理解~

下面写几个力扣的题目方便大家练习
2848. 与车相交的点

class Solution {
    public int numberOfPoints(List<List<Integer>> nums) {
        int max=0;
        for(List<Integer> p : nums)max = Math.max(max,p.get(1));
        int[] diff = new int[max + 2];
        for (List<Integer> interval : nums) {
            diff[interval.get(0)]++;
            diff[interval.get(1) + 1]--;
        }
        int num=0;
        int s=0;
        for(int t:diff){
            s+=t;
            if(s>0)num++;
        }
        return num;
    }
}

1094. 拼车

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] d=new int[1001];
        for(int [] t:trips){
            int num = t[0], start = t[1], end = t[2];
            d[start]+=num;
            d[end]-=num;//不包括end
        }
        int s=0;
        for(int t:d){
            s+=t;
            if(s>capacity)return false;
        }
        return true;
    }
}

1893. 检查是否区域内所有整数都被覆盖

class Solution {
    public boolean isCovered(int[][] ranges, int left, int right) {
        int[] diff = new int[52];
        //对差分数组进行处理
        for(int i = 0; i < ranges.length; i++){
            diff[ranges[i][0]]++;
            diff[ranges[i][1]+1]--;
        }
        //根据差分数组处理前缀和，为理解方便单独定义sum，可以原地做
        int[] sum = new int[52];
        for(int i = 1; i <= 51; i++){
            sum[i] = sum[i-1] + diff[i];
        }
        //从left到right判断是否满足sum > 0
        for(int i = left; i <= right; i++){
            if(sum[i] <= 0) return false;
        }
        return true;
    }
}

1109. 航班预订统计

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] c = new int[n + 1];
        for (int[] bo : bookings) {
            int l = bo[0] - 1, r = bo[1] - 1, v = bo[2];
            c[l] += v;
            c[r + 1] -= v;
        }
        int[] ans = new int[n];
        ans[0] = c[0];
        for (int i = 1; i < n; i++) {
            ans[i] = ans[i - 1] + c[i];
        }
        return ans;
    }
}

2406. 将区间分为最少组数

class Solution {
   public int minGroups(int[][] intervals) {
    int max = intervals[0][1];
    for (int[] interval : intervals) {
        max = Math.max(max, interval[1]);
    }
    int[] diff = new int[max + 1];
    for (int[] interval : intervals) {
        diff[interval[0]] += 1;
        if (interval[1] + 1 <= max) {
            diff[interval[1] + 1] -= 1;
        }
    }
    int t = 0, ans = 0;
    for (int i = 1; i <= max; i++) {
        t = t + diff[i];
        ans = Math.max(ans, t);
    }
    return ans;
}
}

1589. 所有排列中的最大和

class Solution {
    public int maxSumRangeQuery(int[] nums, int[][] requests) {
        int p = (int)1e9 + 7;
        int n = nums.length;
        long ans = 0;
        int[] diff = new int[n + 1];
        Arrays.sort(nums);
        for (int i = 0; i < requests.length; i++) {
            diff[requests[i][0]]++;
            diff[requests[i][1] + 1]--;
        }
        for (int i = 0; i < n; i++) {
            diff[i + 1] += diff[i];
        }
        Arrays.sort(diff);
        for (int i = n; i >= 1 && diff[i] > 0; i--) {
            ans += (long)diff[i] * nums[i - 1];
            ans %= p;
        }
        return (int)ans;
    }
}

二维差分
2536. 子矩阵元素加 1

class Solution {
    public int[][] rangeAddQueries(int n, int[][] queries) {
        // 二维差分
        int[][] diff = new int[n + 2][n + 2];
        for (int[] q : queries) {
            int r1 = q[0], c1 = q[1], r2 = q[2], c2 = q[3];
            diff[r1 + 1][c1 + 1]++;
            diff[r1 + 1][c2 + 2]--;
            diff[r2 + 2][c1 + 1]--;
            diff[r2 + 2][c2 + 2]++;
        }

        // 计算 diff 的二维前缀和（原地修改），然后填入 ans
        int[][] ans = new int[n][n];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1];
                ans[i - 1][j - 1] = diff[i][j];
            }
        }
        return ans;
    }
}