差分数组

差分数组是一种用于高效处理数组区间更新操作的数据结构，核心思想是将区间操作转换为端点操作，将时间复杂度从 O(n) 优化到 O(1)。

核心概念

1. 差分数组定义：
   对于原始数组 arr[0..n-1]，其差分数组 diff 满足：

   • diff[0] = arr[0]
   • diff[i] = arr[i] - arr[i-1]（当 i ≥ 1）

2. 还原原始数组：
   差分数组的前缀和就是原始数组：
   arr[i] = diff[0] + diff[1] + ... + diff[i]

3. 区间更新操作：
   若要将 arr[L..R] 的所有元素增加 val，只需：

   diff[L]   += val;  // 影响从 L 开始的所有位置
   diff[R+1] -= val;  // 抵消 R+1 及之后的位置（若 R+1 < n）
   

优势

• 区间更新时间复杂度：O(1)（相比直接遍历的 O(n)）
• 单次查询时间复杂度：O(n)（通过前缀和还原整个数组）
• 适合先批量更新，最后再查询的场景

---

C++ 示例代码

#include <iostream>
#include <vector>
using namespace std;

// 构建差分数组
vector<int> createDiffArray(const vector<int>& arr) {
    int n = arr.size();
    vector<int> diff(n);
    diff[0] = arr[0];
    for (int i = 1; i < n; i++) {
        diff[i] = arr[i] - arr[i-1];
    }
    return diff;
}

// 区间更新 [L, R] 增加 val
void rangeUpdate(vector<int>& diff, int L, int R, int val) {
    diff[L] += val;
    if (R + 1 < diff.size()) {
        diff[R+1] -= val;
    }
}

// 从差分数组还原原始数组
vector<int> restoreArray(const vector<int>& diff) {
    vector<int> arr(diff.size());
    arr[0] = diff[0];
    for (int i = 1; i < diff.size(); i++) {
        arr[i] = arr[i-1] + diff[i];
    }
    return arr;
}

int main() {
    // 原始数组
    vector<int> arr = {3, 5, 2, 4, 1};
    
    // 构建差分数组
    vector<int> diff = createDiffArray(arr);
    
    // 执行区间更新
    rangeUpdate(diff, 1, 3, 3);  // [5,2,4] 增加3 → [5+3,2+3,4+3]
    rangeUpdate(diff, 0, 2, -1); // [3,5,2] 减少1
    
    // 还原更新后的数组
    vector<int> updatedArr = restoreArray(diff);
    
    // 打印结果
    cout << "原始数组: ";
    for (int num : arr) cout << num << " ";
    
    cout << "\n更新后数组: ";
    for (int num : updatedArr) cout << num << " ";
    
    return 0;
}

输出结果

原始数组: 3 5 2 4 1 
更新后数组: 2 7 4 7 1

关键步骤解析

1. 初始状态：

   • 原始数组 arr = [3, 5, 2, 4, 1]
   • 差分数组 diff = [3, 2, -3, 2, -3]（计算：5-3=2, 2-5=-3, 4-2=2, 1-4=-3）

2. 第一次更新：[1,3] 加 3

   • 修改差分数组：
     • diff[1] += 3 → 2+3=5
     • diff[4] -= 3 → -3-3=-6
   • 此时 diff = [3, 5, -3, 2, -6]

3. 第二次更新：[0,2] 减 1

   • 修改差分数组：
     • diff[0] += (-1) → 3-1=2
     • diff[3] -= (-1) → 2+1=3
   • 最终 diff = [2, 5, -3, 3, -6]

4. 还原数组：

   • arr[0] = 2
   • arr[1] = 2+5 = 7
   • arr[2] = 7-3 = 4
   • arr[3] = 4+3 = 7
   • arr[4] = 7-6 = 1

---

应用场景

1. 批量区间增减操作（如：游戏地图区块修改）
2. 航班预订统计（Leetcode 1109）
3. 公交站客流量统计
4. 任何需要高效处理“区间加法”的场景

提示：差分数组适用于离线查询（先完成所有更新，再统一查询）。若需支持单点查询+区间更新，可结合树状数组或线段树实现。

公交站客流量统计（差分数组应用）

下面是一个使用差分数组高效解决公交站客流量统计问题的C++示例。该问题描述为：给定一系列公交行程（每个行程包含起始站、终点站和乘客数量），需要计算每个公交站的最终客流量。

问题描述

• 有 n 个公交站（编号 0 到 n-1）
• 给定 trips 数组，每个元素为 {start, end, passengers}
  • 表示从 start 站到 end 站（包含两端）每个站点增加 passengers 名乘客
• 需要计算每个公交站的最终总客流量

C++ 实现

#include <iostream>
#include <vector>
using namespace std;

vector<int> calculatePassengerFlow(int n, vector<vector<int>>& trips) {
    // 创建差分数组（初始全0）
    vector<int> diff(n, 0);
    
    // 应用每个行程到差分数组
    for (const auto& trip : trips) {
        int start = trip[0];
        int end = trip[1];
        int passengers = trip[2];
        
        // 区间更新：从start到end站增加passengers
        diff[start] += passengers;
        if (end + 1 < n) {
            diff[end + 1] -= passengers;
        }
    }
    
    // 通过差分数组计算最终客流量（原地计算前缀和）
    for (int i = 1; i < n; i++) {
        diff[i] += diff[i - 1];
    }
    
    return diff;
}

int main() {
    // 示例数据：5个公交站，3个行程
    int n = 5;
    vector<vector<int>> trips = {
        {1, 3, 5},  // 站点1-3各增加5名乘客
        {0, 2, 3},   // 站点0-2各增加3名乘客
        {2, 4, 7}    // 站点2-4各增加7名乘客
    };
    
    // 计算客流量
    vector<int> result = calculatePassengerFlow(n, trips);
    
    // 打印结果
    cout << "公交站客流量统计结果:\n";
    for (int i = 0; i < n; i++) {
        cout << "站点 " << i << ": " << result[i] << " 名乘客\n";
    }
    
    return 0;
}

代码解析

1. 差分数组初始化

vector<int> diff(n, 0);

创建长度为 n（公交站数量）的差分数组，所有元素初始化为0。

2. 处理行程数据

for (const auto& trip : trips) {
    int start = trip[0];
    int end = trip[1];
    int passengers = trip[2];
    
    diff[start] += passengers;
    if (end + 1 < n) {
        diff[end + 1] -= passengers;
    }
}

对每个行程：

• 在起始站 start 处增加乘客数量
• 在终点站后一站 end+1 处减少乘客数量（若存在）

3. 计算最终客流量

for (int i = 1; i < n; i++) {
    diff[i] += diff[i - 1];
}

通过计算差分数组的前缀和，得到每个站点的最终客流量。

示例计算过程

初始差分数组：[0, 0, 0, 0, 0]

1. 处理行程 [1, 3, 5]：

   • diff[1] += 5 → [0, 5, 0, 0, 0]
   • diff[4] -= 5 → [0, 5, 0, 0, -5]

2. 处理行程 [0, 2, 3]：

   • diff[0] += 3 → [3, 5, 0, 0, -5]
   • diff[3] -= 3 → [3, 5, 0, -3, -5]

3. 处理行程 [2, 4, 7]：

   • diff[2] += 7 → [3, 5, 7, -3, -5]

4. 计算前缀和：

   • 站点0: 3
   • 站点1: 3 + 5 = 8
   • 站点2: 8 + 7 = 15
   • 站点3: 15 + (-3) = 12
   • 站点4: 12 + (-5) = 7

程序输出

公交站客流量统计结果:
站点 0: 3 名乘客
站点 1: 8 名乘客
站点 2: 15 名乘客
站点 3: 12 名乘客
站点 4: 7 名乘客

算法优势

1. 时间复杂度：O(n + m)
   • 处理 m 个行程：每个行程 O(1)
   • 计算最终结果：O(n)
2. 空间复杂度：O(n)（仅需一个差分数组）
3. 高效性：比直接遍历每个站点的朴素方法（O(m×n)）快得多，尤其当行程数量大时