区间修改 - 差分

问题描述

最近在刷题的时候，遇到了一类区间修改的问题，刚开始用暴力法做，结果TLE了。后来学了差分数组这个技巧，解决的是区间修改问题，发现效率提升巨大。今天整理一下，分享给大家。

暴力解法

最直接的想法就是老老实实遍历区间，一个一个改：

public class BruteForce {
    public static void rangeUpdate(int[] arr, int left, int right, int val) {
        for (int i = left; i <= right; i++) {
            arr[i] += val;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        
        rangeUpdate(arr, 1, 3, 2);
        System.out.println("操作1后: " + Arrays.toString(arr));
        
        rangeUpdate(arr, 2, 4, -1);
        System.out.println("操作2后: " + Arrays.toString(arr));
    }
}

这种方法简单粗暴，但是效率不高： 时间复杂度：O(m*n)，m是操作次数，n是数组长度。

差分数组优化

核心思想

差分数组的精髓在于：用差值来表示数组，把区间修改变成两个点的修改。

什么意思呢？假设原数组是[1, 2, 3, 4, 5]，它的差分数组是：

diff[0] = 1        // arr[0] = 1
diff[1] = 1        // arr[1] - arr[0] = 1
diff[2] = 1        // arr[2] - arr[1] = 1
diff[3] = 1        // arr[3] - arr[2] = 1
diff[4] = 1        // arr[4] - arr[3] = 1

神奇的地方来了：原数组就是差分数组的前缀和！

arr[0] = diff[0] = 1
arr[1] = diff[0] + diff[1] = 1+1 = 2
arr[2] = diff[0] + diff[1] + diff[2] = 1+1+1 = 3
...

区间修改的技巧

要给区间[left, right]都加上val，只需要：

1. diff[left] += val
2. diff[right+1] -= val

为什么这样就行了？因为当我们计算前缀和还原数组时：

• 从left开始，每个位置都会多加val
• 从right+1开始，又会减掉val，抵消了

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();

        long[] a = new long[n + 1];
        long[] diff = new long[n + 2];
        for (int i = 1; i <= n; i++) {
            a[i] = in.nextLong();
            diff[i] = a[i] - a[i - 1];
        }
        while (m-- > 0) {
            int l = in.nextInt();
            int r = in.nextInt();
            long k = in.nextLong();
            diff[l] += k;
            diff[r + 1] -= k;
        }

        for (int i = 1; i <= n; i++) {
            a[i] = a[i - 1] + diff[i];
        }
        for (int i = 1; i <= n; i++) {
            System.out.print(a[i] + " ");
        }
    }
}

总结

差分数组虽然听起来高大上，但本质就是一个很朴素的思想：用差值来描述变化，通过前缀和来还原状态。它的优势在于把O(n)的区间修改变成了O(1)的操作，当操作次数很多时，效率提升非常明显。