差分基础概念差分是一种常用的算法技巧主要用于高效处理区间更新操作。其核心思想是通过构建差分数组将区间操作转换为单点操作从而将时间复杂度从O(n)降低到O(1)。差分数组的定义对于原数组a其差分数组d满足d[i] a[i] - a[i-1]i 0d[0] a[0]。通过差分数组可以快速实现对原数组某个区间的增减操作。一维差分实现构建差分数组vectorint buildDiff(vectorint a) { int n a.size(); vectorint d(n); d[0] a[0]; for (int i 1; i n; i) { d[i] a[i] - a[i-1]; } return d; }区间更新操作void updateRange(vectorint d, int l, int r, int val) { d[l] val; if (r 1 d.size()) { d[r1] - val; } }还原原数组vectorint restore(vectorint d) { vectorint a(d.size()); a[0] d[0]; for (int i 1; i d.size(); i) { a[i] a[i-1] d[i]; } return a; }二维差分实现二维差分用于处理矩阵的区间更新。定义差分矩阵d[i][j]表示从(0,0)到(i,j)矩形区域的增量。构建差分矩阵vectorvectorint buildDiff2D(vectorvectorint matrix) { int m matrix.size(), n matrix[0].size(); vectorvectorint d(m, vectorint(n, 0)); d[0][0] matrix[0][0]; for (int i 1; i m; i) d[i][0] matrix[i][0] - matrix[i-1][0]; for (int j 1; j n; j) d[0][j] matrix[0][j] - matrix[0][j-1]; for (int i 1; i m; i) { for (int j 1; j n; j) { d[i][j] matrix[i][j] - matrix[i-1][j] - matrix[i][j-1] matrix[i-1][j-1]; } } return d; }子矩阵更新void updateRegion(vectorvectorint d, int x1, int y1, int x2, int y2, int val) { d[x1][y1] val; if (x2 1 d.size()) d[x21][y1] - val; if (y2 1 d[0].size()) d[x1][y21] - val; if (x2 1 d.size() y2 1 d[0].size()) d[x21][y21] val; }还原原矩阵vectorvectorint restore2D(vectorvectorint d) { int m d.size(), n d[0].size(); vectorvectorint mat(m, vectorint(n)); mat[0][0] d[0][0]; for (int i 1; i m; i) mat[i][0] mat[i-1][0] d[i][0]; for (int j 1; j n; j) mat[0][j] mat[0][j-1] d[0][j]; for (int i 1; i m; i) { for (int j 1; j n; j) { mat[i][j] mat[i-1][j] mat[i][j-1] - mat[i-1][j-1] d[i][j]; } } return mat; }典型题目解析题目1区间加法给定一个长度为n的数组初始全为0。进行k次操作每次给区间[l,r]增加val。最后输出整个数组。解法vectorint getModifiedArray(int length, vectorvectorint updates) { vectorint d(length, 0); for (auto update : updates) { int l update[0], r update[1], val update[2]; d[l] val; if (r 1 length) d[r1] - val; } vectorint res(length); res[0] d[0]; for (int i 1; i length; i) { res[i] res[i-1] d[i]; } return res; }题目2航班预订统计有n个航班编号1到n。给定 bookings [[1,2,10],[2,3,20],[2,5,25]]表示从航班1到2各预定10个座位航班2到3各预定20个座位等。返回每个航班的预定总数。解法vectorint corpFlightBookings(vectorvectorint bookings, int n) { vectorint d(n 2, 0); for (auto b : bookings) { d[b[0]] b[2]; d[b[1]1] - b[2]; } vectorint res(n); res[0] d[1]; for (int i 1; i n; i) { res[i] res[i-1] d[i1]; } return res; }题目3子矩阵求和给定一个m×n矩阵处理两种操作1. 更新子矩阵(x1,y1)到(x2,y2)所有元素加val2. 查询子矩阵和。解法class NumMatrix { vectorvectorint diff; vectorvectorint mat; int m, n; public: NumMatrix(vectorvectorint matrix) { m matrix.size(), n matrix[0].size(); mat vectorvectorint(m, vectorint(n, 0)); diff vectorvectorint(m 1, vectorint(n 1, 0)); for (int i 0; i m; i) { for (int j 0; j n; j) { updateRegion(i, j, i, j, matrix[i][j]); } } } void updateRegion(int x1, int y1, int x2, int y2, int val) { diff[x1][y1] val; diff[x21][y1] - val; diff[x1][y21] - val; diff[x21][y21] val; } int sumRegion(int x1, int y1, int x2, int y2) { return mat[x2][y2] - (x10?mat[x1-1][y2]:0) - (y10?mat[x2][y1-1]:0) (x10y10?mat[x1-1][y1-1]:0); } void update() { for (int i 0; i m; i) { for (int j 0; j n; j) { mat[i][j] (i0?mat[i-1][j]:0) (j0?mat[i][j-1]:0) - (i0j0?mat[i-1][j-1]:0) diff[i][j]; } } } };高阶应用题目4最大重叠区间数给定一组区间找出被最多区间覆盖的点。例如[[1,5],[2,6],[3,4]]返回3点3、4都被3个区间覆盖。解法int maxOverlap(vectorvectorint intervals) { mapint, int diff; for (auto inv : intervals) { diff[inv[0]]; diff[inv[1]1]--; } int res 0, cur 0; for (auto p : diff) { cur p.second; res max(res, cur); } return res; }题目5会议室II给定一组会议时间区间问至少需要多少会议室。例如[[0,30],[5,10],[15,20]]返回2。解法int minMeetingRooms(vectorvectorint intervals) { mapint, int diff; for (auto inv : intervals) { diff[inv[0]]; diff[inv[1]]--; } int res 0, cur 0; for (auto p : diff) { cur p.value; res max(res, cur); } return res; }优化技巧离散化处理当数据范围很大但实际数据点较少时可以先离散化再应用差分。多维差分三维甚至更高维的差分可以通过类似二维的容斥原理实现。结合其他数据结构差分数组常与前缀和、线段树等结合使用。常见错误边界处理更新区间[r1]时忘记检查是否越界。初始化问题差分数组初始值应与原数组对应。还原顺序必须先处理完所有更新操作后再还原原数组。扩展练习实现三维差分及其更新操作。解决这个问题给定一个01矩阵每次操作翻转一个子矩阵内的所有元素0变11变0最后统计1的个数。设计一个支持区间加、区间乘、区间查询的数据结构。差分算法通过巧妙的预处理将复杂的区间操作简化为高效的单点操作是算法竞赛和实际工程中处理批量更新的利器。掌握差分技术需要理解其数学原理并通过大量练习熟悉各种变形和应用场景。金融领域的应用在股票或基金分析中差分用于计算每日价格波动。例如某股票连续三天的收盘价为 $[100, 105, 102]$ 元一阶差分为 $[5, -3]$反映涨跌幅度。高频交易中差分可帮助识别短期趋势。气象数据监测气象站通过差分处理每小时温度数据。若某日温度记录为 $[22, 24, 23, 21]$℃差分序列 $[2, -1, -2]$ 显示温度变化速率预警突发降温。运动健康追踪智能手环利用差分计算步频。假设每分钟步数序列为 $[60, 65, 70]$差分为 $[5, 5]$表明用户加速行走。结合加速度传感器数据可优化卡路里消耗模型。工业生产质量控制生产线记录每小时零件尺寸偏差 $[0.1, 0.12, 0.09]$ mm差分为 $[0.02, -0.03]$。若差分绝对值超过阈值 $0.05$触发设备校准指令防止批量次品。注意事项差分对噪声敏感实际应用中常配合移动平均滤波。高阶差分如二阶差分可进一步分析变化率的趋势但需注意数据平稳性要求。