差分数组:原理与应用

136 阅读5分钟

一、什么是差分数组

差分数组是一种高效处理区间更新操作的数据结构技巧,特别适用于需要对数组的某个区间进行频繁增减操作的场景。差分数组的核心思想是通过存储相邻元素的差值而非元素本身,将区间操作转化为端点操作,从而将时间复杂度从O(n)降低到O(1)。

给定一个原始数组arr,其对应的差分数组diff定义为:

diff[i] = arr[i] - arr[i-1] (i > 0)
diff[0] = arr[0] (i = 0)

例如:
原始数组: [1, 3, 6, 8, 5]
差分数组: [1, 2, 3, 2, -3]

二、差分数组的优势

差分数组的主要优势在于它可以高效处理区间更新操作。对于传统的数组,如果我们想对区间[i, j]内的所有元素增加一个值val,需要遍历整个区间进行逐个修改,时间复杂度为O(n)。而使用差分数组,我们只需要修改两个端点:

  1. diff[i] += val
  2. diff[j+1] -= val (如果j+1在数组范围内)

这样就将区间操作的时间复杂度从O(n)降低到了O(1)。

三、差分数组的实现

1. 构建差分数组

vector<int> buildDiffArray(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;
}

2. 区间更新操作

void updateRange(vector<int>& diff, int i, int j, int val) {
    diff[i] += val;
    if (j + 1 < diff.size()) {
        diff[j+1] -= val;
    }
}

3. 还原原始数据

vector<int> restoreArray(const vector<int>& diff) {
    int n = diff.size();
    vector<int> arr(n);
    arr[0] = diff[0];
    for (int i = 1; i < n; ++i) {
        arr[i] = arr[i-1] + diff[i];
    }
    return arr;
}

四、差分数组的应用场景

差分数组特别适用于以下场景:

  1. 频繁的区间增减操作
  2. 需要多次区间操作后查询最终结果
  3. 处理大量区间覆盖问题
  4. 航班预订、会议室安排等问题

五、LeetCode例题解析

1. 航班预订统计(1109. Corporate Flight Bookings)

题目链接:leetcode.com/problems/co…

题目描述:有n个航班,编号从1到n。给定一个航班预订表bookings,其中bookings[i] = [firsti, lasti, seatsi]表示在firsti到lasti的每个航班上预订了seatsi个座位。返回一个长度为n的数组answer,表示每个航班上预订的座位总数。

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    vector<int> diff(n + 1, 0); // 使用n+1大小避免边界检查
    
    for (const auto& booking : bookings) {
        int first = booking[0] - 1; // 转换为0-based
        int last = booking[1] - 1;
        int seats = booking[2];
        
        diff[first] += seats;
        if (last + 1 < n) {
            diff[last + 1] -= seats;
        }
    }
    
    vector<int> answer(n);
    answer[0] = diff[0];
    for (int i = 1; i < n; ++i) {
        answer[i] = answer[i-1] + diff[i];
    }
    
    return answer;
}

2. 拼车(1094. Car Pooling)

题目链接:leetcode.com/problems/ca…

题目描述:一辆车有capacity个座位,给定trips数组,其中trips[i] = [numPassengers, from, to]表示有numPassengers乘客在from上车,在to下车。判断车辆是否能完成所有行程(任何时候乘客数不超过capacity)。

bool carPooling(vector<vector<int>>& trips, int capacity) {
    vector<int> diff(1001, 0); // 题目中0 <= from < to <= 1000
    
    for (const auto& trip : trips) {
        int passengers = trip[0];
        int from = trip[1];
        int to = trip[2];
        
        diff[from] += passengers;
        diff[to] -= passengers;
    }
    
    int current = 0;
    for (int i = 0; i <= 1000; ++i) {
        current += diff[i];
        if (current > capacity) {
            return false;
        }
    }
    
    return true;
}

3. 区间加法(370. Range Addition)

题目链接:leetcode.com/problems/ra…

题目描述:给定一个初始长度为length的全0数组,和一系列更新操作updates,其中updates[i] = [startIdx, endIdx, inc],表示将子数组[startIdx, endIdx]中的每个元素增加inc。返回执行完所有操作后的数组。

vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
    vector<int> diff(length, 0);
    
    for (const auto& update : updates) {
        int start = update[0];
        int end = update[1];
        int inc = update[2];
        
        diff[start] += inc;
        if (end + 1 < length) {
            diff[end + 1] -= inc;
        }
    }
    
    vector<int> result(length);
    result[0] = diff[0];
    for (int i = 1; i < length; ++i) {
        result[i] = result[i-1] + diff[i];
    }
    
    return result;
}

六、差分数组的变种与扩展

1. 二维差分数组

差分数组的概念可以扩展到二维,用于处理二维矩阵的区间更新问题。二维差分数组的更新需要修改四个角:

// 更新矩形区域(x1,y1)到(x2,y2)
void update2D(vector<vector<int>>& diff, int x1, int y1, int x2, int y2, int val) {
    diff[x1][y1] += val;
    if (x2 + 1 < diff.size()) {
        diff[x2+1][y1] -= val;
    }
    if (y2 + 1 < diff[0].size()) {
        diff[x1][y2+1] -= val;
    }
    if (x2 + 1 < diff.size() && y2 + 1 < diff[0].size()) {
        diff[x2+1][y2+1] += val;
    }
}

2. 差分数组与线段树的比较

差分数组和线段树都可以处理区间更新问题,但各有优劣:

特性差分数组线段树
区间更新复杂度O(1)O(logn)
单点查询复杂度O(n)O(logn)
空间复杂度O(n)O(n)
实现难度简单较复杂

选择依据:

  • 如果只有区间更新,最后才查询结果,选择差分数组
  • 如果需要边更新边查询,选择线段树

七、总结

差分数组是一种简单而强大的技巧,特别适合处理大量区间更新操作后查询结果的场景。它通过将区间操作转化为端点操作,大幅提高了算法效率。掌握差分数组不仅可以帮助我们解决许多LeetCode问题,在实际工程中也有广泛应用,如资源调度、时间线处理等场景。

通过本文的三个LeetCode例题,我们可以看到差分数组如何优雅地解决看似复杂的问题。建议读者在理解基本原理后,多练习相关题目,以加深对这一技巧的掌握。