差分数组定义性质及用途

1.定义

对于一个长度大小为n的数组arr[n] 我们可以建立他的差分数组f[n]。其中f[i] = arr[i] - arr[i-1]。 
例如 f[2] = arr[2] - arr[1]。

2.性质

(1) 可通过差分数组计算arr[i]的值：
	arr[i] = f[i] + f[i-1] + ... + f[0]  或 arr[i] = f[i] + arr[i-1]
(2) 计算数组每一项的前缀和：
	![在这里插入图片描述](https://www.icode9.com/i/ll/?i=2021051111293737.png#pic_center)
	这里简单解释一下： 如果要求sum2 则sum2 = arr[0] + arr[1] + arr[2] 
	而每个arr[i] = f[i] + f[i-1] + ... + f[0]  故 sum2的求解中 f[0]出现3次 f[1]出现2次 f[2] 1次
	故sum[2] = 3 * f[0] + 2 * f[1] + 1 * f[2]

3.用途

(1) 区间快速加减操作：
	假如现在对数列中区间[L,R]上的数加上x，我们通过性质(1)知道，第一个受影响的差分数组中的元素为f[L],
即令f[L]+=x，那么后面数列元素在计算过程中都会加上x；最后一个受影响的差分数组中的元素为f[R],
所以令f[R+1]-=x，即可保证不会影响到R以后数列元素的计算。这样我们不必对区间内每一个数进行处理，
只需处理两个差分后的数即可。
(2) 询问区间和
	求区间[l, r]的和即为 sum[R] - sum[L-1]  

例题 LeetCode1109

import java.util.Arrays;

public class Solution {
    
    // 原数组
    private int[] arr;
    // 差分数组
    private int[] f;
    
    public int[] corpFlightBookings(int[][] bookings, int n) {
        arr = new int[n];
        f = new int[n];
        int l = 0;
        int r = 0;
        int seats = 0;
        for (int i = 0; i < bookings.length; i++) {

            // 注意我们维护的数组下标从0开始 所以要减去偏移量1
            l = bookings[i][0] - 1;
            r = bookings[i][1] - 1;
            seats = bookings[i][2];
            // 差分数组f[l, r] 中 f[l]要加上座位数
            f[l] += seats;
            // f[r+1]如果超过数组长度 也continue
            if (r + 1 >= n)
                continue;
            // 差分数组右边界下一个数值要减去 增加的座位数
            f[r+1] -= seats;
        }
        // 根据差分数组求出最终结果
        arr[0] = f[0];
        for (int i = 1; i < n; i++) {
            arr[i] = f[i] + arr[i-1];
        }
        return arr;
    }

    public static void main(String[] args) {
        int[][] commend = {{1,2,10},{2,3,20},{2,5,25}};
        int[] res = new Solution().corpFlightBookings(commend, 5);
        for (int num : res)
            System.out.print(num + " ");
    }
}