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

差分数组：原理与应用

ops 2025/8/16 10:55:09

一、什么是差分数组

差分数组是一种高效处理区间更新操作的数据结构技巧，特别适用于需要对数组的某个区间进行频繁增减操作的场景。差分数组的核心思想是通过存储相邻元素的差值而非元素本身，将区间操作转化为端点操作，从而将时间复杂度从O(n)降低到O(1)。

给定一个原始数组arr，其对应的差分数组diff定义为：

diff[i] = arr[i] - arr[i-1] (i > 0)
diff[0] = arr[0] (i = 0)

例如：
原始数组: [1, 3, 6, 8, 5]
差分数组: [1, 2, 3, 2, -3]

二、差分数组的优势

差分数组的主要优势在于它可以高效处理区间更新操作。对于传统的数组，如果我们想对区间[i, j]内的所有元素增加一个值val，需要遍历整个区间进行逐个修改，时间复杂度为O(n)。而使用差分数组，我们只需要修改两个端点：

diff[i] += val
diff[j+1] -= val (如果j+1在数组范围内)

这样就将区间操作的时间复杂度从O(n)降低到了O(1)。

三、差分数组的实现

1. 构建差分数组

vector<int> buildDiffArray(const vector<int>& arr) {int n = arr.size();vector<int> diff(n);diff[0] = arr[0];for (int i = 1; i < n; ++i) {diff[i] = arr[i] - arr[i-1];}return diff;
}

2. 区间更新操作

void updateRange(vector<int>& diff, int i, int j, int val) {diff[i] += val;if (j + 1 < diff.size()) {diff[j+1] -= val;}
}

3. 还原原始数据

vector<int> restoreArray(const vector<int>& diff) {int n = diff.size();vector<int> arr(n);arr[0] = diff[0];for (int i = 1; i < n; ++i) {arr[i] = arr[i-1] + diff[i];}return arr;
}

四、差分数组的应用场景

差分数组特别适用于以下场景：

频繁的区间增减操作
需要多次区间操作后查询最终结果
处理大量区间覆盖问题
航班预订、会议室安排等问题

五、LeetCode例题解析

1. 航班预订统计（1109. Corporate Flight Bookings）

题目链接：https://leetcode.com/problems/corporate-flight-bookings/

题目描述：有n个航班，编号从1到n。给定一个航班预订表bookings，其中bookings[i] = [firsti, lasti, seatsi]表示在firsti到lasti的每个航班上预订了seatsi个座位。返回一个长度为n的数组answer，表示每个航班上预订的座位总数。

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {vector<int> diff(n + 1, 0); // 使用n+1大小避免边界检查for (const auto& booking : bookings) {int first = booking[0] - 1; // 转换为0-basedint last = booking[1] - 1;int seats = booking[2];diff[first] += seats;if (last + 1 < n) {diff[last + 1] -= seats;}}vector<int> answer(n);answer[0] = diff[0];for (int i = 1; i < n; ++i) {answer[i] = answer[i-1] + diff[i];}return answer;
}

2. 拼车（1094. Car Pooling）

题目链接：https://leetcode.com/problems/car-pooling/

题目描述：一辆车有capacity个座位，给定trips数组，其中trips[i] = [numPassengers, from, to]表示有numPassengers乘客在from上车，在to下车。判断车辆是否能完成所有行程（任何时候乘客数不超过capacity）。

bool carPooling(vector<vector<int>>& trips, int capacity) {vector<int> diff(1001, 0); // 题目中0 <= from < to <= 1000for (const auto& trip : trips) {int passengers = trip[0];int from = trip[1];int to = trip[2];diff[from] += passengers;diff[to] -= passengers;}int current = 0;for (int i = 0; i <= 1000; ++i) {current += diff[i];if (current > capacity) {return false;}}return true;
}

3. 区间加法（370. Range Addition）

题目链接：https://leetcode.com/problems/range-addition/

题目描述：给定一个初始长度为length的全0数组，和一系列更新操作updates，其中updates[i] = [startIdx, endIdx, inc]，表示将子数组[startIdx, endIdx]中的每个元素增加inc。返回执行完所有操作后的数组。

vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {vector<int> diff(length, 0);for (const auto& update : updates) {int start = update[0];int end = update[1];int inc = update[2];diff[start] += inc;if (end + 1 < length) {diff[end + 1] -= inc;}}vector<int> result(length);result[0] = diff[0];for (int i = 1; i < length; ++i) {result[i] = result[i-1] + diff[i];}return result;
}

六、差分数组的变种与扩展

1. 二维差分数组

差分数组的概念可以扩展到二维，用于处理二维矩阵的区间更新问题。二维差分数组的更新需要修改四个角：

// 更新矩形区域(x1,y1)到(x2,y2)
void update2D(vector<vector<int>>& diff, int x1, int y1, int x2, int y2, int val) {diff[x1][y1] += val;if (x2 + 1 < diff.size()) {diff[x2+1][y1] -= val;}if (y2 + 1 < diff[0].size()) {diff[x1][y2+1] -= val;}if (x2 + 1 < diff.size() && y2 + 1 < diff[0].size()) {diff[x2+1][y2+1] += val;}
}