【蓝桥杯】一学就会的小技巧（二）：差分

🍑前言：

• 一学就会的小技巧（一）：前缀和
• 一学就会的小技巧（三）：快速幂
• 一学就会的小技巧（四）：龟速乘
• 一学就会的小技巧（五）：矩阵快速幂
• 一学就会的小技巧（六）：矩阵快速幂的应用
• 数论基础—素数筛、最大公约数、最小公倍数
• 省赛真题—K倍区间（前缀和，数学，思维）

🍹🍹差分跟前缀和类似，不过它主要用于区间修改，在对数组进行n次区间修改后，利用差分可以快速得到修改后的新数组。

题目传送门：🚀🚀🚀

🍓差分：

797. 差分（一维差分模板题）

输入一个长度为n的整数序列。

接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数n和m。

第二行包含n个整数，表示整数序列。

接下来m行，每行包含三个整数l，r，c，表示一个操作。

输出格式

共一行，包含n个整数，表示最终序列。

数据范围

1≤n,m≤1000001≤n,m≤100000,
1≤l≤r≤n1≤l≤r≤n,
−1000≤c≤1000−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000−1000≤整数序列中元素的值≤1000

输入样例：

6 31 2 2 1 2 11 3 13 5 11 6 1

输出样例：

3 4 5 3 4 2

👩🏻‍🏫在输入时引入一个新数组diff[]记录num[i]与num[i - 1]的差：

⭐通过diff[]数组可以求出num[]的每一项，num[i] = diff[1] + diff[2] + ... + diff[i]。

☕经过第一次区间修改1 3 1：

☕对区间1~3的值全部加1，可以发现diff[]数组只有diff[1]与diff[4]的值发生了改变，diff[1]+1，diff[4]-1。

☕经过第二次区间修改3 5 1：

☕经过第三次区间修改1 6 1：

⭐可以看到，对于每次区间修改l r c，diff[]只有两个位置会发生变化，那么我们只需要维护这两个位置就可以了，其中diff[l] = diff[l] + c，diff[r] = diff[r] - c。

⭐最后如果要得到修改后的原数组，只需要一次遍历diff[]，对其求前缀和即可，时间复杂度$O(N)$。

🍦Java代码：

import java.util.Scanner;public class Main {    public static int[] num = new int[10005];    // 记录相邻两项差，数组要开的大一些，防止越界    public static int[] diff = new int[10005];    public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); for (int i = 1; i <= n; i++) {     num[i] = sc.nextInt();     diff[i] = num[i] - num[i - 1]; } for (int i = 0; i < m; i++) {     int l = sc.nextInt();     int r = sc.nextInt();     int c = sc.nextInt();     diff[l] += c;     diff[r + 1] -= c;  } sc.close(); // 利用diff[]得到原数组，差分数组求前缀和 int sum = 0; for (int i = 1; i <= n; i++) {     sum += diff[i];     num[i] = sum;     System.out.print(num[i] + " "); }    }}

🍌🍌🍌
本文介绍了第二个小技巧——差分，跟前缀和类似，同样通过预处理的方式，记录相邻两项的差值，从而在经过多次区间修改后，快速求得修改后的原数组~
🍍🍍🍍
创作不易，如果觉得本文对你有所帮助的话请动动小手，给博主点个免费的赞吧。🙇🏻‍♀️
🍉🍉🍉
@作者：Mymel_晗，计科专业大学牲菜狗一枚，请大佬们多多关照~