小而美的算法技巧：差分数组

class PrefixSum {
private:
    vector<int> prefix;

public:
    // 前缀和数组
    PrefixSum(vector<int>& nums) {
        prefix = vector<int>(nums.size() + 1);
        // 计算 nums 的累加和
        for (int i = 1; i < nums.size() + 1; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
    }

    // 查询闭区间 [i, j] 的累加和
    int query(int i, int j) {
        return prefix[j + 1] - prefix[i];
    }
};

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

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

// 差分数组工具类
class Difference {
    // 差分数组
    private:
        vector<int> diff;
    
    // 输入一个初始数组，区间操作将在这个数组上进行
    public:
        Difference(vector<int>& nums) {
            diff = vector<int>(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) {
            diff[i] += val;
            if (j + 1 < diff.size()) {
                diff[j + 1] -= val;
            }
        }

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

void increment(int i, int j, int val) {
    diff[i] += val;
    if (j + 1 < sizeof(diff)/sizeof(int)) {
        diff[j + 1] -= val;
    }
}

class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        // nums 初始化为全 0
        vector<int> nums(length, 0);
        // 构造差分解法
        Difference df(nums);
        
        for (auto& update : updates) {
            int i = update[0];
            int j = update[1];
            int val = update[2];
            df.increment(i, j, val);
        }
        
        return df.result();
    }
};

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n)

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        // nums 初始化为全 0
        vector<int> nums(n);
        // 构造差分解法
        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();
    }
};

bool carPooling(vector<vector<int>>& trips, int capacity);

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        // 最多有 1001 个车站
        vector<int> nums(1001);
        
        // 构造差分解法
        Difference df(nums);
        
        for (vector<int> trip : trips) {
            // 乘客数量
            int val = trip[0];
            
            // 第 trip[1] 站乘客上车
            int i = trip[1];
            
            // 第 trip[2] 站乘客已经下车，
            // 即乘客在车上的区间是 [trip[1], trip[2] - 1]
            int j = trip[2] - 1;
            
            // 进行区间操作
            df.increment(i, j, val);
        }
        
        vector<int> res = df.result();
        
        // 客车自始至终都不应该超载
        for (int i = 0; i < res.size(); i++) {
            if (capacity < res[i]) {
                return false;
            }
        }
        return true;
    }
};