AI summary
type
status
date
slug
summary
category
tags
icon
password
本文讲一个和前缀和思想非常类似的算法技巧「差分数组」，差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。
比如说，我给你输入一个数组 nums，然后又要求给区间 nums[2..6] 全部加 1，再给 nums[3..9] 全部减 3，再给 nums[0..4] 全部加 2，再给...
一通操作猛如虎，然后问你，最后 nums 数组的值是什么？
常规的思路很容易，你让我给区间 nums[i..j] 加上 val，那我就一个 for 循环给它们都加上呗，还能咋样？这种思路的时间复杂度是 O(N)，由于这个场景下对 nums 的修改非常频繁，所以效率会很低下。
这里就需要差分数组的技巧，类似前缀和技巧构造的 preSum 数组，我们先对 nums 数组构造一个 diff 差分数组，diff[i] 就是 nums[i] 和 nums[i-1] 之差。diff[0]=nums[0]，通过差分数组可以反推出原始数组。
这样构造差分数组 diff，就可以快速进行区间增减的操作，如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可。
现在我们把差分数组抽象成一个类，包含 increment 方法和 result 方法：

370. 区间加法

假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k 个更新的操作。
其中，每个操作会被表示为一个三元组：[startIndex, endIndex, inc]，你需要将子数组 A[startIndex ... endIndex]（包括 startIndex 和 endIndex）增加 inc。
请你返回 k 次操作后的数组。
直接考察了差分数组技巧，相当于给你输入一个长度为 n 的 nums 数组，其中的元素初始值都为 0，让你对其中的区间元素进行增减操作，最后返回最终的 nums 数组。
直接照搬上面写的 Difference 类即可：

1109. 航班预订统计

这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。
这个题目就在那绕弯弯，其实它就是个差分数组的题，我给你翻译一下：
给你输入一个长度为 n 的数组 nums，其中所有元素都是 0。再给你输入一个 bookings，里面是若干三元组 (i, j, k)，每个三元组的含义就是要求你给 nums 数组的闭区间 [i-1,j-1] （航班编号从 1 开始）中所有元素都加上 k。请你返回最后的 nums 数组是多少？

1094. 拼车

车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。
trips[i] 代表着一组区间操作，那么 nums 数组元素就是每一站的乘客数。只要数组中的元素都小于 capacity ，就说明可以接送所有乘客。
题目给了 0<=trips[i][1]<trips[i][2]<=1000 ，那么数组大小可以设为 1001。
注意：第 trip[2] 站乘客先下后上，所以乘客在车上的区间是 [trip[1], trip[2] - 1]。