当前位置：首页 > ds >正文

区间修改 - 差分

ds 2025/8/12 8:52:47

文章目录

问题描述
暴力解法
差分数组优化
- 核心思想
- 区间修改的技巧
- 代码实现
总结

问题描述

最近在刷题的时候，遇到了一类区间修改的问题，刚开始用暴力法做，结果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，只需要：

diff[left] += val
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] + " ");}}
}