➖ Difference Array – Mảng hiệu

🎯 Mục tiêu bài học

1. Đặt vấn đề

1.1. Cách làm trực tiếp

Với mỗi thao tác, duyệt từ L đến R và cộng x vào từng phần tử.

1.2. Quan sát quan trọng

Khi cộng x vào đoạn [L,R], mức tăng bắt đầu từ L và kết thúc ngay sau R:

• Tại L: bắt đầu cộng thêm x.
• Tại R+1: hủy tác động bằng cách trừ x.

2. Định nghĩa và công thức

3. Mô phỏng tạo mảng hiệu

4. Mô phỏng cập nhật đoạn

5. Difference Array 2D

Với ma trận, ta có thể cộng x vào toàn bộ hình chữ nhật từ (x1,y1) đến (x2,y2) bằng bốn mốc:

6. Phân tích thuật toán

7. Code mẫu

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<long long> a(n);
    for (long long &x : a) cin >> x;

    vector<long long> diff(n);

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

    while (q--) {
        int left, right;
        long long value;
        cin >> left >> right >> value;

        --left;
        --right;

        diff[left] += value;

        if (right + 1 < n) {
            diff[right + 1] -= value;
        }
    }

    a[0] = diff[0];

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

    for (long long x : a) {
        cout << x << ' ';
    }
}

int n, q;
cin >> n >> q;

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

while (q--) {
    int left, right;
    long long value;

    cin >> left >> right >> value;
    --left;
    --right;

    diff[left] += value;
    diff[right + 1] -= value;
}

vector<long long> a(n, 0);
long long current = 0;

for (int i = 0; i < n; i++) {
    current += diff[i];
    a[i] = current;
}

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

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<long long>> diff(
        n + 2,
        vector<long long>(m + 2, 0)
    );

    while (q--) {
        int x1, y1, x2, y2;
        long long value;

        cin >> x1 >> y1 >> x2 >> y2 >> value;

        diff[x1][y1] += value;
        diff[x1][y2 + 1] -= value;
        diff[x2 + 1][y1] -= value;
        diff[x2 + 1][y2 + 1] += value;
    }

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << diff[i][j] << ' ';
        }
        cout << '\n';
    }
}

def apply_range_updates(a, updates):
    n = len(a)
    diff = [0] * n

    diff[0] = a[0]

    for i in range(1, n):
        diff[i] = a[i] - a[i - 1]

    for left, right, value in updates:
        diff[left] += value

        if right + 1 < n:
            diff[right + 1] -= value

    result = [0] * n
    result[0] = diff[0]

    for i in range(1, n):
        result[i] = result[i - 1] + diff[i]

    return result

8. Giải thích code

8.1. Vì sao diff[i] = a[i] - a[i-1]?

diff[i] biểu diễn mức thay đổi khi đi từ vị trí i−1 sang i. Khi cộng dồn các mức thay đổi, ta nhận lại giá trị ban đầu.

8.2. Vì sao chỉ sửa L và R+1?

diff[L] += x làm mọi prefix từ L trở đi tăng x. diff[R+1] -= x hủy mức tăng từ vị trí R+1, nên chỉ đoạn L đến R bị ảnh hưởng.

8.3. Vì sao phải kiểm tra R+1 < n?

Nếu R là phần tử cuối, không có vị trí R+1 trong mảng diff kích thước n. Có thể tránh nhánh này bằng cách cấp phát diff kích thước n+1.

8.4. Vì sao dùng long long?

8.5. Tại sao cập nhật 2D dùng bốn góc?

Hai dấu cộng bắt đầu vùng tác động; hai dấu trừ hủy tác động theo hàng và cột. Góc dưới phải bị trừ hai lần nên phải cộng lại một lần.

8.6. Có thể query ngay sau mỗi update không?

Không hiệu quả nếu phải khôi phục toàn bộ mảng sau từng cập nhật. Difference Array phù hợp khi gom tất cả update trước rồi dựng kết quả một lần.

9. Lỗi thường gặp

• Quên đổi chỉ số 1-based của đề sang 0-based trong code.
• Quên kiểm tra R+1 < n.
• Dùng dấu cộng tại R+1 thay vì dấu trừ.
• Khôi phục mảng bằng công thức sai.
• Nhầm Difference Array với Prefix Sum.
• Dùng Difference Array khi cần query xen kẽ update.
• Dùng int cho dữ liệu tổng lớn.
• Trong 2D, quên cộng lại góc (x2+1,y2+1).
• Với mảng ban đầu khác 0, quên tạo diff từ a trước khi update.

10. Quiz và bài tập