2025 - 03 - 08 - 第 69 篇
Author: 郑龙浩 / 仟濹
【一维差分】

前缀和与差分 - 我的博客

一维前缀和
【算法 C/C++】一维前缀和
一维差分
【算法 C/C++】一维差分
二维前缀和
【算法 C/C++】二维前缀和
二维差分
【算法 C/C++】二维差分

差分(一维)

1 大体介绍

举例的数组

// 原数组
int arr[5] = {1, 3, 7, 5, 2};
// “原数组”的“差分数组” - 原生差分数组
int arr_d[5] = {1, 2, 4, -2, -3};
// 计算“差分数组”的“前缀和数组” --> 又变成了原数组
int sum_d[5] = {1, 3, 7, 5, 2};

(1)1 原数组 2 差分数组 3 差分数组的前缀和数组

// 原数组
1, 3, 7, 5, 2
// “原数组”的“差分数组” - 原生差分数组
1, 2, 4, -2, -3
// 计算“差分数组”的“前缀和数组” --> 又变成了原数组
1, 3, 7, 5, 2

差分数组

原生差分数组就是除了 arr_d[0] 外，其余 arrr_d[i] 都是 arr_d[ i ] = arr[i] - arr[i - 1]

说白了除了第一个元素是原封不动存入新的数组，其余的都是存储的后一个元素减去前一个元素的结果，重新存入一个新的数组

// “原数组”的“差分数组”
int arr_d[5] = {1, 2, 4, 2, -3};

原生差分数组 做前缀和计算 –> 原数组

当原生差分数组做前缀和计算的时候，会还原回原数组

// “原数组”的“差分数组” - 原生差分数组
int arr_d[5] = {1, 2, 4, 2, -3};
// 计算“差分数组”的“前缀和数组” --> 又变成了原数组
int sum_d[5] = {1, 3, 7, 5, 2};

（2）记录区间操作的边界

在增量差分数组中进行标记 –> 标记边界

当对 >=1 个区间进行加减value操作的时候，可以只计算 头 ** 和 尾，然后进行差分计算和前缀和计算**就可以得出加减的结果

( 无需再和以前一样通过循环进行累加操作了，节省了运算时间，提升了效率 )

Eg: [left, right] + value 的时候

操作如下

arr[left] += value;
arr[right + 1] -= value;

有多少个区间进行了 + value 操作，就循环多少次如上的操作

2 差分原理是什么？？？

这个原理想了挺久的，刚开始确实没明白，本来打算死记下来差分的步骤就好了，后来又看了一边网课，大致明白了，下面写一下

**一维差分 ** 的思路

define N 10
int arr_d[N] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

然后我想要对区间 [2, 6] 中所有的元素进行加 1 操作，则 原生差分数组 d[N] 的变化如下

• arr[left] += value;
• arr[right + 1] -= value;

// 下标:
 0  1  2  3  4  5  6  7  8  9
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
// 变化后 --> d[2] + 1 且 d[6 + 1] - 1
{0, 0, 1, 0, 0, 0, 0,-1, 0, 0}

前缀和操作

为什么是arr_d[2] + 1 且 arr_d[6 + 1] - 1呢，这个实际上就是确定了 要进行 +1 操作的区间，从 arr_d[2] 开始做前缀和计算，直到d[7]

过程：

从 d[2]开始做前缀和计算，答案一直为 1，直到加到d[6+1]的时候，此时d[7]为-1，1 + (-1)答案为 0，也就是到这 +1操作截止了。

回过头去看过程，不就是利用差分数组确定要 +1 的区间吗。

结果为:

{0, 0, 1, 1, 1, 1, 1, 0, 0, 0}

那么进行了前缀和计算的差分数组是存储的什么呢？？？

实际上存储的就是所有元素要进行 +- 的 value

所以，接下来的操作就是根据存储着所有位置要加减什么值得前缀和数组计算出不同区间+不同值得最终结果

增量差分数组！！！

注意区分，我上面的介绍均为 原生差分数组，因为课程中这么写的，我也就这样记得，后来写这个差分代码才意识到问题，又问了AI，才明白其实是并不是用的 这个原生差分数组，而是增量差分数组，然后增量差分数组刚开始并不是存储的每个位置的增量(增量差分数组在应用前缀和之前存储的是区间操作的边界标记。通过前缀和操作以后才是存储的每个位置的增量。

操作区间	标记方式	意义
区间开始（left）	delta[left] += value	从位置left开始累积增加value
区间结束（right）	delta[right+1] -= value	在位置right+1取消value的累积

而在写程序的时候用 增量差分数组，直接存储每个元素位置的增量即可，而这个增量既可以是正也可以是负。

实际上在程序实现中，并不直接存储原数组的差分值，即不适用原生差分数组，而是通过 区间操作标记 来记录每个位置的增量变化(只存储增量)，初始时 d 数组全为0，每个区间操作 [left, right] + value 会修改 d[left] 和 d[right + 1]，最终通过 前缀和计算 得到每个位置的总增量值。这些增量值会叠加到原数组上，完成最终的区间修改操作。

3 总结一下过程

假设现在所有的数值已经输入

//变量
arr[N] - 原数组
d[N] - 增量差分数组 - 刚开始存储的是区间操作的边界标记 - 前缀和操作后存储每个元素的增量

1. 对增量差分数组 d[N] 进行如下操作，每个区间操作对应一次修改。

   d[left] += value；
   if (right + 1 < N) d[right + 1] -= value; // 防止越界
   

   此过程用来计算 区间操作标记的位置

2. 利用 d[N]进行前缀和计算，这时候计算得出来的才是 每个元素的增量

   for (int i = 1; i < N; i++) {
       d[i] += d[i - 1];  // 此时 d[i] 表示 arr[i] 的增量
   }
   

3. 然后 将 d[N] 数组和 arr[N] 数组的所有元素进行一对一的相加操作，得出将增量值叠加到原数组的结果

   for (int i = 0; i < N; i++) {
       arr[i] += d[i];
   }
   

4 某些区间所有的元素 + 某数(不使用差分)

题目

有一个数组 arr[5] = {1, 3, 7, 5, 2}，将如下区间内的元素加上指定的数字：

[2, 4] + 5, [1, 3] + 2, [0, 2] - 3，并打印更改后的数组

答案为：-2, 2, 11, 12, 7

思路

原来的方法就是，直接硬将这些区间内的数字±操作，当计算区间过多的时候，运算时间太长

比如计算 arr[2]的计算，就要进行三次运算 arr[2] + 5 + 2 - 3，最终得出11，如果有好多的话，太麻烦了

代码

// Author: 郑龙浩 / 仟濹
// 2025-03-06
// 有一个数组 `arr[5] = {1, 3, 7, 5, 2}`，将如下区间内的元素加上指定的数字：
// `[2, 4] + 5, [1, 3] + 2, [0, 2] - 3`，并打印更改后的数组
// 答案为：`-2, 2, 11, 12, 7 `
// 差分
#include <iostream>
#include <algorithm>
using namespace std;
#define N 5
// 方法2
// #define get_sum(a, b) (a ? sum[b] - sum[a - 1] : sum[b])
int arr[ N ] = {1, 3, 7, 5, 2}; // 原数组
int d[ N ] = { 0 }; // 全部置为0
// 利用“差分数组”存储需要改变的范围以及值
void arr_add(int left, int right, int value){
    d[ left ] += value;
    // 避免越界
    if( right + 1 < N) d[ right + 1] -= value; 
}
int main( void ){
    arr_add(2, 4, 5);
    arr_add(1, 3, 2);
    arr_add(0, 2, -3);
    // 对差分数组进行前缀和计算
    for( int i = 1; i < N; i ++ ){
        d[ i ] += d[i - 1];
    }
    // 将最终要加的值加到 arr[N] 原数组当中
    for( int i = 0; i < N; i ++ ){
        arr[ i ] += d[ i ];
    }
    // 打印结果
    for( int i = 0; i < N; i ++ ){
        cout << arr[ i ] << " ";
    }
    return 0;
}

5 某些区间所有的元素 + 某数(使用差分)

题目

有一个数组 arr[5] = {1, 3, 7, 5, 2}，将如下区间内的元素加上指定的数字：

[2, 4] + 5, [1, 3] + 2, [0, 2] - 3，并打印更改后的数组

答案为：-2, 2, 11, 12, 7

思路

前面也写过了

//变量
arr[N] - 原数组
d[N] - 差分数组

1. 对原数组中的数据进行如下操作，有多少个区间进行 +value 操作就操作多少遍

   d[left] += value, d[right + 1] -= value;
   

   此过程用来计算差分数组中的值，而差分数组实际上就是存储的就是 对原数组的不同区间的加减不同的值为多少

2. 利用 d[N]进行前缀和计算，计算出每个元素应该 ± 多少

3. 然后 将 d[N] 数组和 arr[N] 数组的所有元素进行一对一的相加操作，得出最终答案。

代码

// Author: 郑龙浩 / 仟濹
// 2025-03-06
// 有一个数组 `arr[5] = {1, 3, 7, 5, 2}`，将如下区间内的元素加上指定的数字：
// `[2, 4] + 5, [1, 3] + 2, [0, 2] - 3`，并打印更改后的数组
// 答案为：`-2, 2, 11, 12, 7 `
// 差分
#include <iostream>
#include <algorithm>
using namespace std;
#define N 5
int arr[ N ] = {1, 3, 7, 5, 2}; // 原数组
int d[ N ] = { 0 }; // 全部置为0
// 利用“差分数组”存储需要改变的范围以及值
void arr_add(int left, int right, int value){
    d[ left ] += value;
    d[ right + 1] -= value; 
}
int main( void ){
    arr_add(2, 4, 5);
    arr_add(1, 3, 2);
    arr_add(0, 2, -3);
    // 对差分数组进行前缀和计算
    for( int i = 1; i < N; i ++ ){
        d[ i ] += d[i - 1];
    }
    // 将最终要加的值加到 arr[N] 原数组当中
    for( int i = 0; i < N; i ++ ){
        arr[ i ] += d[ i ];
    }
    // 打印结果
    for( int i = 0; i < N; i ++ ){
        cout << arr[ i ] << " ";
    }
    return 0;
}