资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

差分数组详解：算法领域中的区间更新利器

创作时间:

作者:

@小白创作中心

差分数组详解：算法领域中的区间更新利器

引用

CSDN

https://blog.csdn.net/2401_82648291/article/details/144865478

差分数组是算法领域中一个非常实用的数据结构，特别适用于处理数组的区间更新操作。通过差分数组，可以在O(1)的时间复杂度内完成区间更新，相比直接在原始数组上遍历更新（时间复杂度为O(len)，len为区间长度）效率大大提升。本文将系统地介绍差分数组的概念、原理、应用场景以及优缺点，并通过具体的代码示例帮助读者更好地理解。

一、差分数组基础

1.1 概念

差分数组是基于一个原始数组构建出来的辅助数组，用于更高效地处理原始数组上的区间修改操作以及后续的查询操作。

设原始数组为nums，长度为n：

diff[0] = nums[0]
对于i > 0，diff[i] = nums[i] - nums[i - 1]

1.2 区间更新操作

基本原理：

当需要对原始数组nums的区间[left, right]（left和right为区间的左右边界索引，索引从 0 开始）进行统一的增量操作（比如每个元素都加上值val）时，利用差分数组可以高效地完成更新，只需执行diff[left] += val和diff[right + 1] -= val（需确保right + 1在差分数组合法索引范围内，若right + 1 >= n则不用执行后面这一步）操作即可，这样就能在O(1)时间复杂度内完成区间更新。

代码实现：

// 对差分数组进行区间更新操作
void updateDiff(vector<int>& diff, int left, int right, int val) {
    diff[left] += val;
    int n = diff.size();
    if (right + 1 < n) {
        diff[right + 1] -= val;
    }
}

1.3 还原原始数组

基本原理：

可以通过差分数组diff还原出原始数组nums，计算方式为：

nums[0] = diff[0]
对于i > 0，nums[i] = nums[i - 1] + diff[i]

代码实现：

// 根据差分数组还原原始数组
vector<int> getOriginalArray(vector<int>& diff) {
    int n = diff.size();
    vector<int> nums(n);
    nums[0] = diff[0];
    for (int i = 1; i < n; ++i) {
        nums[i] = nums[i - 1] + diff[i];
    }
    return nums;
}

二、差分数组的优缺点

2.1 优点

高效的区间更新操作：当需要对原始数组的某个区间进行相同的更新操作（如增减一个固定值）时，差分数组展现出了卓越的时间效率。例如，对原始数组nums的区间[left, right]的每个元素加上值val，直接操作原始数组需要遍历区间内的每个元素，时间复杂度为O(right-left+1)。而使用差分数组，只需进行两次操作：diff[left]+=val和diff[right + 1]-=val（假设right + 1不超出数组范围），时间复杂度为O(1)。
便于记录变化过程：差分数组可以清晰地记录原始数组每个位置的变化量。通过观察差分数组，能够直观地了解原始数组在哪些位置发生了变化以及变化的幅度。
支持动态更新和查询：在面对一系列动态的区间更新操作后，仍然能够相对高效地查询原始数组任意位置的值。可以通过前缀和的方式，预先处理差分数组，使得查询原始数组某一位置的值的时间复杂度降低到O(1)。

2.2 缺点

空间开销：需要额外的空间来存储差分数组。如果原始数组规模很大，差分数组的空间占用可能会成为一个问题。
理解和实现的复杂性：相较于直接对原始数组进行操作，差分数组的概念和操作逻辑相对复杂。对于初学者来说，理解差分数组的原理以及正确地实现相关操作需要花费一定的时间和精力。
应用场景的局限性：差分数组主要适用于区间更新频繁且需要查询更新后数组元素的场景。如果只是偶尔进行单点更新或者不需要查询更新后的数组，使用差分数组可能会增加不必要的复杂性和空间开销。

三、差分数组的应用场景

3.1 区间统计问题

在数据统计领域，差分数组常用于处理区间统计问题。例如，在统计一段时期内的销售数据变化情况时，原始数组记录每天的销售额，差分数组可以用于记录每天销售额的增减量。

3.2 数组区间更新场景

在很多算法问题和实际应用中，经常会遇到对数组进行区间更新的情况。例如，在图像像素处理中，对图像的某个矩形区域内的像素进行统一的亮度调整或者颜色通道值的修改。

3.3 动态规划中的状态转移优化

在动态规划问题中，有些状态转移方程涉及到区间的更新和查询。差分数组可以作为一种优化手段，减少状态转移过程中的计算量。

四、差分数组实战

下面通过一道蓝桥杯的题目来应用差分数组：

4.1 题目描述

题目链接：小明的彩灯

4.2 题目分析

首先，理解题意：每次给出的分别是左右区间，以及要加的值；我们只需要根据区间去进行相应操作就行；但是，最后不是直接把原数组返回，要注意到：

数据范围（也因此我们使用了long long而不是int）
操作完后；如果原数组值变成了负数就要把它改成0

4.3 差分数组应用

步骤：

差分数组填充：我们这里对于差分数组是多开了两个空间：因为：

其一，就是让区间端值和下标一一对应
其二，就是在更新差分数组的时候可能出现越界（diff[end + 1] -= val）
```
vector<ll>diff(N + 2);//差分数组
```

多次操作：

vector<pair<pair<ll, ll>, ll>> oper(Q + 1);//存储每组操作变量
for (int i = 1; i <= Q; i++) cin >> oper[i].first.first >> oper[i].first.second >> oper[i].second;
int j = 1;
//根据每次操作及时更新原数组对应的差分数组：
while (Q--) {
    ll start = oper[j].first.first, end = oper[j].first.second, val = oper[j].second;
    diff[start] += val;
    diff[end + 1] -= val;//这里注意越界；如果是最后一个下标则可能越界，故差分数组要再多开一个
    j++;
}

原数组更新并完成打印操作：

for (int i = 1; i <= N; i++)v[i] = v[i - 1] + diff[i];//数次操作后根据差分数组还原原数组
v.erase(v.begin());//删除虚拟节点
for (auto a : v) {
    ll t = a >= 0 ? a : 0;//由题意知，负数为0
    cout << t << " ";
}