差分数组+前缀和——小而美的算法

目次
  前言
  一、差分数组是什么？
  差分数组的界说
  差分数组的作用
  差分数组的性子
  二、应用
  1.Leetcode-1109航班预定统
  总结
  

---

前言

近来，做题的时间总是会用到数组范围内增减变量，差分数组和前缀和便能从O(n)->O(1)，可以低沉时间复杂度。以是，这篇短文重要就是纪录一下差分数组和前缀和的性子、本事和应用。

一、差分数组是什么？

差分数组的界说

差分数组：差分数组就是原始数组相邻元素之间的差。
着实差分数组是一个辅助数组，从侧面来体现给定某一数组的厘革，一样平常用来对数组举行区间修改的利用。
比如说某一个数组【1，2，3，4，5，6，7】，将其区间【1，4】的数值全部加上3，着实当原始数组中元素同时加上大概减掉某个数，那么他们的差分数组着实是不会厘革的.

差分数组的作用

差分数组的作用就是求多次举行区间修改后的数组。构造出差分数组，就可以快速举行区间增减了。淹灭O(1)的时间修改 diff 数组，就相称于给原数组的整个区间做了修改。
留意 ：只能是区间元素同时增长或镌汰类似的数的情况才气用。
差分数组的性子

1）对于原始数组arr[a, b, c, d]，其差分数组为：diff[a, b-a, c-b, d-c]
2）差分数组的前缀和数组 == 原始数组，即：求差分数组的前缀和数组，即可还原归去。[a, a + b-a, a+b-a + c-b, ...]
3）对原始数组的区间增长，可以转化为对其差分数组的两点增长（ O(n) -> O(1) ）： 假设对arr[i ... j]区间每个元素全部增长delta，则等价于：diff += delta，diff[j+1] -= delta
二、应用

1.Leetcode-1109航班预定统计

   这里有 n 个航班，它们分别从 1 到 n 举行编号。
  有一份航班预订表 bookings ，表中第 i 条预订纪录 bookings = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包罗 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
  请你返回一个长度为 n 的数组 answer，内里的元素是每个航班预定的座位总数。
  
  示例 1：

1. <strong>输入：</strong>bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
2. <strong>输出：</strong>[10,55,45,25,25]
3. <strong>解释：</strong>
4. 航班编号        1   2   3   4   5
5. 预订记录 1 ：   10  10
6. 预订记录 2 ：       20  20
7. 预订记录 3 ：       25  25  25  25
8. 总座位数：      10  55  45  25  25
9. 因此，answer = [10,55,45,25,25]

复制代码

示例 2：

1. <strong>输入：</strong>bookings = [[1,2,10],[2,2,15]], n = 2
2. <strong>输出：</strong>[10,25]
3. <strong>解释：</strong>
4. 航班编号        1   2
5. 预订记录 1 ：   10  10
6. 预订记录 2 ：       15
7. 总座位数：      10  25
8. 因此，answer = [10,25]

复制代码

  提示：
  

• 1 <= n <= 2 * 10^4
  
• 1 <= bookings.length <= 2 * 10^4
  
• bookings.length == 3
  
• 1 <= firsti <= lasti <= n
  
• 1 <= seatsi <= 10^4
  

本题，说成人话就是，给你输入一个长度为n的数组nums，此中全部元素都是0.再给你输入一个bookings，内里是多少三元组（i，j，k），每个三元组的寄义就是要求你给nums数组的闭区间【i-1,j-1】中全部元素都加上k。请你返回末了的nums数组是多少？
如许看来，这就是范例的一道差分数组模板题了，可以设start =  bookings[0]，end = bookings[1],delta  = bookings[2]。然后对委曲点，举行改变。末了求前缀和就可以求出答案了。
代码实现如下：

1. class Solution {
2.     public int[] corpFlightBookings(int[][] bookings, int n) {
3.         int[] diff = new int[n];
4.         for (int[] booking : bookings) {
5.             int start = booking[0], end = booking[1], delta = booking[2];
6.             diff[start - 1] += delta;
7.             if (end < n) {
8.                 diff[end] -= delta;
9.             }
10.         }
12.         for (int i = 1; i < n; i++) {
13.             diff[i] += diff[i - 1];
14.         }
15.         return diff;
16.     }
18. }

复制代码

---

总结

个人感觉，差分数组是与前缀和数组所对应的一种逆利用，类似于求导和积分，也就是说，对差分数组求前缀和，可以得到原数组，同样的，对前缀和数组求差分，也可以得到原数组。当我们必要对原数组的差别区间施加差别的增量，我们只要按规则修改差分数组即可。