差分数组的性质

1. 定义 ： 对于已知有n个元素的离线数列d，我们可以建立记录它每项与前一项差值的差分数组f：显然，f[1]=d[1]-0=d[1];对于整数i∈[2,n]，我们让f[i]=d[i]-d[i-1]。
2. 性质 ： 原数组可以用差分数组的前缀和求得。
3. 用途： 3.1 快速处理区间[left, right]上的数加x，通过性质可知道，第一个受影响的差分数组元素为f[left], 即令f[left]+=x, 那么之后的元素在计算过程中都会加上x。 最后一个受影响的查分数组元素为f[right],所以在f[right+1]处需要矫正，即f[right+1]-=x，即可保证right+1之后的元素不被影响。这样的话不必对[left,right]范围之内所有数进行处理。
4. leetcode例题： 1109. 航班预订统计

题目
  这里有 n ：个航班，它们分别从 1 到 n 进行编号。

  有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

  请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i 上预订的座位总数。

python:
class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        ans = [0]*n
        for l, r, s in bookings:
            ans[l-1] += s
            if r < n:
                ans[r] -= s
        for i in range(1, n):
            ans[i] += ans[i-1]
        return ans
        
        
C++:
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> ans (n);
        for (auto& book : bookings){
            ans[book[0]-1] += book[2];
            if (book[1] < n){
                ans[book[1]] -= book[2];
            }
        }
        for (int i = 1; i < n; i++){
            ans[i] += ans[i-1];
        }
        return ans;
    }
};