专题 - 差分.md

差分

问题: 多次操作, 每个操作对l ~ r范围进行一次区间+c操作

转化为差分问题 => diff[l] += a & diff[r+1] -= a(如果r+1不越界)

如果原始数组有初始值 => diff[i] += x & diff[i+1] -= x(视作一次长度为1的差分)

最后再对diff数组求前缀和恢复到原始数组

LC1109. 航班预定统计

直观的差分问题, 注意下标从0开始

// 对某个范围[param1, param2]进行一次区间加操作 => 差分
vector<int> diff;
void diff_operation(int l, int r, int c){
    diff[l] += c;
    diff[r+1] -= c;
}
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    diff.resize(n+1);
    for(vector<int> op: bookings){
        int l = op[0]-1;
        int r = op[1]-1;
        int c = op[2];
        diff_operation(l, r, c);
    }
    vector<int> prefixSum(n, 0);
    prefixSum[0] = diff[0];
    for(int i=1; i<n; i++){
        prefixSum[i] = prefixSum[i-1] + diff[i];
    }
    return prefixSum;
}

https://leetcode.cn/problems/corporate-flight-bookings

LC1094. 拼车

注意index开始位置为 0, 与LC1109. 航班预定统计不同

对于prefixSum[0]也要判断capacity

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        // 计算差分(Index 从 0 开始)
        int maxLen = 0;
        vector<int> diff(1001, 0);
        for(vector<int> t: trips){
            diff[t[1]] += t[0];
            diff[t[2]] -= t[0];
            maxLen = max(maxLen, max(t[1], t[2]));
        }
        // 这里的前缀和省略为两个cumSum即可
        // int cumSum = diff[0];
        vector<int> prefixSum(maxLen+1, 0);
        prefixSum[0] = diff[0];
        if(prefixSum[0] > capacity)
            return false;
        for(int i=1; i<=maxLen; i++){
            prefixSum[i] = prefixSum[i-1]+diff[i];
            if(prefixSum[i] > capacity)
                return false;
        }
        return true;
    }
};

https://leetcode.cn/problems/car-pooling/

253. 会议室II: map存储的差分

这道题如果直接用diff数组, 范围已经到了0 <= starti < endi <= 10^6

所以考虑用普通哈希表存储, 但最后也要按从低到高的顺序求和 ➡️ 所以要用key有序的数据结构 ➡️ map

💡受到这个帖子的启发, 里面的vector<PII>➕sort其实就等于map

// [start, end]范围更大的「1094. 拼车」
int minMeetingRooms(vector<vector<int>>& intervals) {
    map<int, int> diff;
    for(vector<int> &interval : intervals){
        int l = interval[0], r = interval[1];
        diff[l] += 1;
        diff[r] -= 1;
    }
    int ans = 0;
    int preSum = 0;
    for(auto &[k, v]: diff){
        preSum += v;
        ans = max(ans, preSum);
    }
    return ans;
}

二维差分

• d[x1][y1] += c
• d[x2+1][y1] -= c
• d[x1][y2+1] -= c
• d[x2+1][y2+1] += c

最后再对diff求二维前缀和映射回原空间

vector<vector<int> > diff(m+1, vector<int>(n+1, 0));

vector<vector<int> > operation(int v, int x1, int y1, int x2, int y2){
    // 对 x1, y1, x2, y2进行边界判断
    diff[x1][y1] += v;
    diff[x2+1][y1] -= v;
    diff[x1][y2+1] -= v;
    diff[x2+1][y2+1] += v;

    // 对diff求前缀和, 映射回原矩阵
    return preSum(diff);
}

2536. 子矩阵元素加 1

注意diff[][]没有偏移, prefixSum[][]有偏移

void diff_operation(vector<vector<int>>& diff, int x1, int y1, int x2, int y2, int c){
    diff[x1][y1] += c;
    diff[x1][y2+1] -= c;
    diff[x2+1][y1] -= c;
    diff[x2+1][y2+1] += c;
}
vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
    vector<vector<int>> diff(n+1, vector<int>(n+1, 0));
    for(vector<int> &q: queries){
        diff_operation(diff, q[0], q[1], q[2], q[3], 1);
    }
    // 对diff[][]求前缀和得到a[][]
    vector<vector<int>> a(n+1, vector<int>(n+1, 0));
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            a[i][j] = diff[i-1][j-1] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
        }
    }
    // 消除前缀和矩阵的错位
    vector<vector<int>> ans(n, vector<int>(n, 0));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            ans[i][j] = a[i+1][j+1];
        }
    }
    return ans;
}

https://leetcode.cn/problems/increment-submatrices-by-one/

2132. 用邮票贴满网格图

todo