Range Addition - Cộng dồn trên đoạn mảng hiệu quả

Cho mảng kích thước n khởi tạo bằng 0. Thực hiện k phép cập nhật, mỗi phép là triplet [startIndex, endIndex, inc]: tăng mỗi phần tử trong đoạn A[startIndex...endIndex] thêm inc. Trả về mảng sau tất cả phép cập nhật.

Ví dụ: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]] → kết quả [-2,0,3,5,3].

Giải thuật (Difference Array / Mảng sai phân)

Thay vì cập nhật từng phần tử, đánh dấu tại start cộng inc, tại end+1 trừ inc (nếu trong phạm vi). Sau đó tính tiền tố (prefix sum) để lấy mảng kết quả. Độ phức tạp O(n + k).

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> getModifiedArray(int n, vector<vector<int>>& a) {
        vector<int> ret(n, 0);
        for (int i = 0; i < a.size(); i++) {
            int l = a[i][0];
            int r = a[i][1] + 1;
            ret[l] += a[i][2];
            if (r < n) ret[r] -= a[i][2];
        }
        for (int i = 1; i < n; i++)
            ret[i] += ret[i - 1];
        return ret;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{1,3,2},{2,4,3},{0,2,-2}};
    print_vector(ob.getModifiedArray(5, v));
    return 0;
}

Đầu vào

5, {{1,3,2},{2,4,3},{0,2,-2}}

Đầu ra

[-2, 0, 3, 5, 3, ]