差分数组

介绍

差分数组本质上也是一个数组，我们暂且定义差分数组为d，差分数组d的大小和原来arr数组大小一样，而且d[i]=arr[i]-arr[i-1]，且d[i]=0，它的含义是什么？就是原来数组i位置上的元素和i-1位置上的元素作差，得到的值就是d[i]的值。

如果需要对L-R范围内所有数都进行相同的操作，我们不需要从L-R遍历arr然后在每个值上进行相同操作，只需要在差分数组d中改变L和R+1的值即可。但是在查询arr数组中某个位置的数时，却要根据差分数组从前往后递推求值。

所以，该方法适用于区间频繁修改，而且这个区间范围是比较大的，离线查询的情况。

栗子

1674. 使数组互补的最少操作次数

给你一个长度为 偶数 n 的整数数组 nums 和一个整数 limit 。每一次操作，你可以将 nums 中的任何整数替换为 1 到 limit 之间的另一个整数。

如果对于所有下标 i（下标从 0 开始），nums[i] + nums[n - 1 - i] 都等于同一个数，则数组 nums 是 互补的 。例如，数组 [1,2,3,4] 是互补的，因为对于所有下标 i ，nums[i] + nums[n - 1 - i] = 5 。

返回使数组 互补 的 最少 操作次数。

思路

有n个数字，即n/2个数对，每个数字的取值范围是1limit，所以显然一个数对的和的取值范围是22 * limit。
我们用一个数组arr[ ]来记录将所有数对和转化成某一个数需要的操作次数，其中arr[i]表示将所有数对和转化成i需要的次数。
接下来我们举几个例子寻找一下规律：
假设数组是1,3,4,2。limit = 5，则第一个数对为（1,2）
我们找出每一个数对的最大值max和最小值min。

如图中数对，将该数对和转化成3所需要的操作次数显然是0，接下来还要讨论转化次数为1和转化次数为2的情况。
显然转化1次能取到的最小值是min + 1，能取到的最大值是max + limit，那么在这范围之外的就是需要转化次数2次。
所以对于每一对数对：分如下几种情况

1. 在[2, min]这个区间，arr[i] += 2;
2. 在[min + 1, min + max]区间，arr[i] += 1;
3. 在min + max上，arr[i] += 0;
4. 在[min + max + 1, max + limit]区间上，arr[i] += 1;
5. 在[max + limit + 1, limit + limit]区间上，arr[i] += 2;

对于上述的操作，是典型的区间加减，需要用到差分数组

class Solution {
    public int minMoves(int[] nums, int limit) {
        int[] diff = new int[limit * 2 + 1];
        for (int i = 0; i < nums.length / 2; i++) {
            int max = Math.max(nums[i], nums[nums.length - i - 1]);
            int min = Math.min(nums[i], nums[nums.length - i - 1]);
            if (min == 1) {
                diff[2] += 1;
            } else{
                diff[2] += 2;
                diff[min + 1] -= 1;
            }
            diff[max + min] -= 1;
            if (max + min + 1 < diff.length) {
                diff[max + min + 1] += 1;
            }
            if (max + limit + 1 < diff.length) {
                diff[max + limit + 1] += 1;
            }
        }
        int now = 0, res = nums.length / 2;
        for (int i = 2; i < diff.length; i++) {
            now += diff[i];
            res = Math.min(res, now);
        }
        return res;
    }
}