文章目录

• • 查分数组定义
  • 应用举例
  • • LeetCode 1109 题「[航班预订统计]

      查分数组定义

      差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

      

      通过这个 diff 差分数组是可以反推出原始数组 nums 的，代码逻辑如下：

      int res[diff.size()];
      // 根据差分数组构造结果数组
      res[0] = diff[0];
      for (int i = 1; i < diff.size(); i++) {
          res[i] = res[i - 1] + diff[i];
      }
      

      应用举例

      LeetCode 1109 题「[航班预订统计]

      • 题目描述

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

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

        请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

        • 实现

          class Solution {
          public:
              /* http://www.codebaoku.com/it-c/it-c-227293.html */
               查分数组工具类C++
              class Difference {
              public:
                      /* 输⼊⼀个初始数组，区间操作将在这个数组上进⾏, 初始化查分数组*/
                      Difference(vector nums)
                      {
                          if (nums.empty()) {
                              return;
                          }
                          diff.resize(nums.size());
                          diff[0] = nums[0];
                          for (int i = 1; i < nums.size(); i++) {
                              diff[i] = nums[i] - nums[i-1];
                          }
                      }
              
                      /* 给闭区间 [i, j] 增加 val（可以是负数）*/
                      void increment(int i, int j, int val) { // NUms为diff的前缀和
                          diff[i] += val;
                          if (j + 1 < diff.size())
                          {
                              diff[j + 1] -= val;
                          }
                      }
              
                      /* 返回结果数组 */
                      vector result()
                      {
                          vector res(diff.size());
                          // 根据差分数组构造结果数组
                          res[0] = diff[0];
                          for (int i = 1; i < diff.size(); i++)
                          {
                              res[i] = res[i - 1] + diff[i];
                          }
                          return res;
                      }
              private:
                  vector diff; // 差分数组
              };
              vector corpFlightBookings(vector>& bookings, int n) {
                  vector nums(n);  // 原始数组初始化为0
                  Difference df(nums);
                  for (auto &booking : bookings) {
                      int i = booking[0] - 1;
                      int j = booking[1] - 1;
                      int val = booking[2];
                      // 对区间nums[i, j]增加val
                      df.increment(i, j, val);
                  }
                  // 返回最终的结果数组
                  return df.result();
              }
          };