数据结构--差分数组（含题目）＜基础入门＞

定义：差分数组是一种处理数据的技巧，主要用于高效地执行区间修改操作。在一个数组中，如果需要频繁地对某个区间的所有元素执行相同的操作（如加或减一个常数），直接遍历并更新区间内的每个元素会非常耗时。差分数组通过只修改区间的端点来实现整个区间的快速更新，大幅降低了操作的时间复杂度。

简单来说，差分数组被创造用来处理区间的加减问题（我是这么理解的），所以以后如果在题目中看到对某一个区间的所有数进行加减操作的，可以先想到运用差分数组来思考。如果向更加深入的了解差分数组的本质，可以自己通过阅读书籍。先来看一个差分入门的题目：

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int a[N];//原数组
int d[N];//差分数组
int n,m;
void revise(int l,int r,int c){d[l]+=c;d[r+1]-=c;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++) revise(i,i,a[i]);while(m--){int l,r,c;cin>>l>>r>>c;revise(l,r,c);}for(int i=1;i<=n;i++){d[i]+=d[i-1];}for(int i=1;i<=n;i++) cout<<d[i]<<" ";
}

上面这个题目是对一个区间进行加操作，完成后输出原数组。我们只需要在区间的开头加上这个数，然后在区间结尾的下一个数减去这个数就可以了。因为差分数组其实是前缀和的逆运算。举个例子，假设原数组是a，差分数组是b，则有a[0] = b[0]，b[1] = a[1] - a[0]，b[2] = a[2] - a[1]，....以此类推，假设初始化完差分数组的时候，如果我们需要得到a[2]，那么就是a[2] = b[2] + b[1] + b[0]。毫无疑问，这就是算差分数组的前缀和。回到上面，假设区间为[l, r]，在b[l]上加c，相当于从l开始到结尾的数都加上了c，在b[r + 1]减去了c，相当于从r+1开始到结尾都减去了c，这就实现了区间[l,r]上的加c操作而没有影响到其他的数。模板就是上面的reverse函数：

void revise(int l,int r,int c){d[l]+=c;d[r+1]-=c;
}

接下来是一些leetcode上面的题目，对于理解差分数组有很大的帮助。

2848. 与车相交的点

这道题目是典型的差分数组，主要思路是给每个区间上都加上1，累计答案时判断如果此时这个点的值大于0，则说明被覆盖了。以下是我的代码：

Python：

python">class Solution:def numberOfPoints(self, nums: List[List[int]]) -> int:max_end = max(end for _, end in nums)diff = [0] * (max_end + 2)for s, e in nums:diff[s] += 1diff[e + 1] -= 1s = 0 #用来计算前缀和res= 0for c in range(max_end + 1):s += diff[c]if (s > 0):res += 1return res

C++：

class Solution:def numberOfPoints(self, nums: List[List[int]]) -> int:maxx = (max(end for _, end in nums) + 1)a = [0] * (maxx + 2)for start, end in nums:a[start] += 1a[end + 1] -= 1return sum(s > 0 for s in accumulate(a))

1893. 检查是否区域内所有整数都被覆盖

这个题和上面的题目大同小异，主要的思路就是：用差分数组的思想将range数组里面的区间上的数都标记一遍，最后算答案的时候遍历，看[left, right]区间上的数是否有a[x] <= 0的，如果有，返回false，反之，返回True。

Python:

python">class Solution:def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:max_end = max(end for _, end in ranges)a = [0] * (max_end + 2)for start, end in ranges:a[start] += 1a[end + 1] -= 1for i in range(1, max_end + 2):a[i] += a[i - 1]for x in range(left, right + 1):if x >= max_end + 2 or a[x] <= 0:return Falsereturn True

C++:

class Solution {
public:bool isCovered(vector<vector<int>>& ranges, int left, int right) {int max_end = std::ranges::max(ranges, {}, [](const auto& a) {return a[1];})[1];vector<int> diff(max_end + 2);for (auto x: ranges) {diff[x[0]] += 1;diff[x[1] + 1] -= 1;}for (int i = 1; i < max_end + 2; i ++) {diff[i] += diff[i - 1];}for (int x = left; x <= right; x ++ ) {if (x >= max_end + 2 || diff[x] <= 0) {return false;}}return true;}
};

1854. 人口最多的年份

主要思路是：用一个数组a来统计logs上区间上的点出现的次数，如果最后从小到大遍历年份，算出出现次数最多的年份即可。

Python：

python">class Solution:def maximumPopulation(self, logs: List[List[int]]) -> int:offset = 1950a = [0] * 101for s, e in logs:a[s - offset] += 1a[e - offset] -= 1mx = 0res = 0cur = 0for i in range(101):cur += a[i]if cur > mx:mx = curres = ireturn res + offset

C++：

class Solution {
public:int maximumPopulation(vector<vector<int>>& logs) {vector<int> mi_vector = std::ranges::min(logs, {}, [](auto& x) {return x[0];});int mi = mi_vector[0];vector<int> mx_vector = std::ranges::max(logs, {}, [](auto& x) {return x[1];});int mx = mx_vector[1];vector<int> a(mx + 2);for (auto x: logs) {a[x[0]] += 1;a[x[1]] -= 1; }int res = 0, diff = 0;int s = 0;for (int i = mi; i <= mx; i ++) {s += a[i];if (s > diff) {res = i;diff = s;}}return res;}
};

改良后的版本，速度快了。

class Solution {
public:int maximumPopulation(vector<vector<int>>& logs) {// vector<int> mi_vector = std::ranges::min(logs, {}, [](auto& x) {//     return x[0];// });// int mi = mi_vector[0];// 换了一种求最小(大)值的方法，速度变快了很多auto mi = std::ranges::min_element(logs, {}, [](const auto& x) {return x[0];});// vector<int> mx_vector = std::ranges::max(logs, {}, [](auto& x) {//     return x[1];// });// int mx = mx_vector[1];auto mx = std::ranges::max_element(logs, {}, [](const auto& x) {return x[1];});vector<int> a((*mx)[1] + 2);for (auto x: logs) {a[x[0]] += 1;a[x[1]] -= 1; }int res = 0, diff = 0;int s = 0;for (int i = (*mi)[0]; i <= (*mx)[1]; i ++) {s += a[i];if (s > diff) {res = i;diff = s;}}return res;}
};

2960. 统计已测试设备

这个题目和以往直接对区间进行加减操作的题目有一点不一样，就是只有在

s + batteryPercentages[i] <= 0

的时候才会进行处理，不过思想也都是一样的。

Python:

class Solution:def countTestedDevices(self, batteryPercentages: List[int]) -> int:n = len(batteryPercentages)cnt = [0] * (n + 1)ans = s = 0for i in range(n):s += cnt[i]if (s + batteryPercentages[i] <= 0):ans += 1else:cnt[i + 1] -= 1return n - ans

C++:

class Solution {
public:int countTestedDevices(vector<int>& batteryPercentages) {int n = batteryPercentages.size();vector<int> cnt(n + 1);int ans = 0;int s = 0;for (int i = 0; i < n; i ++) {s += cnt[i];if (s + batteryPercentages[i] <= 0) {ans ++;}else {cnt[i + 1] -= 1;}}return n - ans;}
};

1094. 拼车

这个题目和之前的题目差不多，都是直接对区间进行操作，不再赘述！！！！

Python：

python">class Solution:def carPooling(self, trips: List[List[int]], capacity: int) -> bool:mx = max(to for _, _, to in trips)a = [0] * (mx + 2)s = 0for num, fm, to in trips:a[fm] += numa[to] -= numfor i in range(mx + 2):s += a[i]if (s > capacity):return Falsereturn True

C++：

class Solution {
public:bool carPooling(vector<vector<int>>& trips, int capacity) {vector<int> x = std::ranges::max(trips, {}, [](const auto& x) {return x[2];});int mx = x[2];vector<int> a(mx + 2);for (const auto& x: trips) {a[x[1]] += x[0];a[x[2]] -= x[0];}int s = 0;for (int i = 0; i < mx + 2; i ++) {s += a[i];if (s > capacity) {return false;}}return true;}
};

1109. 航班预订统计

Python：

python">class Solution:def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:a = [0] * (n + 2)for l, r, num in bookings:a[l] += numa[r + 1] -= numans = []s = 0for i in range(n):s += a[i + 1]ans.append(s)return ans

C++：

class Solution {
public:vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {vector<int> a(n + 2);for (const auto& x: bookings) {a[x[0]] += x[2];a[x[1] + 1] -= x[2];}vector<int> ans;int s = 0;for (int i = 1; i <= n; i ++) {s += a[i];ans.push_back(s);}return ans;}
};

3355. 零数组变换 I

Python：

python">class Solution:def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:n = len(nums)a = [0] * (n + 2)for l, r in queries:a[l] -= 1a[r + 1] += 1s = 0for i in range(n):s += a[i]if s + nums[i] > 0:return Falsereturn True

C++：

class Solution {
public:bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {int n = nums.size();vector<int> cnt(n + 2);for (const auto & x: queries) {cnt[x[0]] -= 1;cnt[x[1] + 1] += 1;}int s = 0;for (int i = 0; i < n; i ++) {s += cnt[i];if (s + nums[i] > 0) {return false;}}return true;}
};

56. 合并区间

这个题目有两种解法，一种是贪心+排序，一种是差分数组的解法。在这里讲一下差分数组的解法，这题是一个变种的差分数组。我们需要将范围映射到原来的两倍，不然就会出现错误，例如样例为[1, 4],[5, 6]就会通过不了。做的改变如下：

贪心解法代码：

C++：

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {if(intervals.size() == 0){return {};}sort(intervals.begin(),intervals.end());vector<vector<int>>ans;for(int i = 0; i < intervals.size(); i ++){int l =intervals[i][0], r = intervals[i][1];if(!ans.size() || ans.back()[1] < l){ans.push_back({l, r});}else{ans.back()[1] = max(ans.back()[1], r);}}return ans;}
};

差分数组解法代码：

Python：

python">class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:mi = min(s for s, _ in intervals)mx = max(e for _, e in intervals)diff = [0] * (2 * mx + 2)ans = [] for s, e in intervals:diff[2 * s] += 1diff[2 * e + 1] -= 1s, l = 0, -1for i in range(len(diff)):s += diff[i]# 刚开始if s > 0:if (l == -1):l = i // 2# 此时结束了elif (s == 0):if (l != -1):ans.append([l, i // 2])l = -1return ans
"""
intervals = 
[[1,4],[5,6]]
"""

C++：

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {auto max_it = std::ranges::max_element(intervals, {}, [](const auto& x) {return x[1];});int mx = (*max_it)[1];vector<int> diff(2 * mx + 2);for (auto x: intervals) {diff[2 * x[0]] += 1;diff[2 * x[1] + 1] -= 1;}vector<vector<int>> ans;int l = -1; //起点int s = 0;for (int i = 0; i <= 2 * mx + 1; i ++) {s += diff[i];if (s > 0) {if (l == -1) {l = i / 2;}}else if (s == 0) {if (l != -1) {ans.push_back({l, (i) / 2});l = -1;}}}return ans;}
};

57. 插入区间

这题和合并区间大同小异，只是多了一个区间的判断。

Python：

python">class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:mx = 0if len(intervals) > 0:mx = max(end for _, end in intervals)mx = max(mx, newInterval[1])cnt = [0] * (2 * mx + 2)for s, e in intervals:cnt[s * 2] += 1cnt[e * 2 + 1] -= 1cnt[2 * newInterval[0]] += 1cnt[2 * newInterval[1] + 1] -= 1ans, l , s = [], -1, 0for i in range(len(cnt)):s += cnt[i]if s > 0:if (l == -1):l = i // 2else:if (l != -1):ans.append([l, i // 2])l = 0return ans

C++：

    class Solution {public:vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {vector<int> mx;if (intervals.size() > 0) {vector<int> mx = std::ranges::max(intervals, {}, [](const auto& x) {return x[1];});}vector<vector<int>> ans;vector<int> diff(2 * max(mx[1], newInterval[1]) + 2);for (const auto& x: intervals) {diff[2 * x[0]] += 1;diff[2 * x[1] + 1] -= 1;}diff[2 * newInterval[0]] += 1;diff[2 * newInterval[1]  + 1] -= 1;int s = 0, start = -1;for (int i = 0; i < diff.size(); i ++) {s += diff[i];if (s > 0) {if (start == -1) {start = i / 2;}}else if (s <= 0) {if (start != -1) {ans.push_back({start, i / 2});// 重新找一个区间的开始位置，需要重新定义一下，而不是直接初始化为i / 2start = -1;}}}return ans;}};

732. 我的日程安排表 III

主要思路是：统计每一个区间上每一个点出现的次数，然后每一个使用book方法时，输出最大值。统计的方法用差分数组来统计！！！！！

C++：

class MyCalendarThree {
map<int, int> cnt;
public:MyCalendarThree() {}int book(int startTime, int endTime) {cnt[startTime] += 1;cnt[endTime] -= 1; int total = 0, ans = 0;for (auto [x, y]: cnt) {total += y;ans = max(ans, total);}return ans;}
};/*** Your MyCalendarThree object will be instantiated and called as such:* MyCalendarThree* obj = new MyCalendarThree();* int param_1 = obj->book(startTime,endTime);*/

Python：

python">class MyCalendarThree:def __init__(self):self.cnt = SortedDict()def book(self, startTime: int, endTime: int) -> int:ans = total = 0self.cnt[startTime] = self.cnt.get(startTime, 0) + 1self.cnt[endTime] = self.cnt.get(endTime, 0) - 1for x in self.cnt.values():total += xans = max(ans, total)return ans# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# param_1 = obj.book(startTime,endTime)

差分数组的练习暂且到此为止了，后续还会持续更新差分数组的题目！如果看到这里想必你也很累了吧，休息一下！！再继续学习！！

数据结构--差分数组（含题目）＜基础入门＞

相关文章

动态规划(路径问题）

c++ map/multimap容器学习笔记

Deepseek的RL算法GRPO解读

go gin配置air

机试题——考古学家

idea对jar包内容进行反编译

设计模式-建造者模式、原型模式

Python从0到100（八十六）：神经网络-ShuffleNet通道混合轻量级网络的深入介绍