➕ Prefix Sum

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

1. Đặt vấn đề

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

Mỗi truy vấn duyệt từ L đến R và cộng từng phần tử.

1.2. Quan sát quan trọng

Nếu biết tổng từ đầu đến R và tổng từ đầu đến L−1, ta lấy hiệu:

2. Ý tưởng và định nghĩa

3. Mô phỏng xây Prefix Sum

4. Mô phỏng truy vấn tổng đoạn

5. Prefix Sum 2D

Dùng để tính tổng hình chữ nhật trên ma trận trong O(1).

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> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + a[i];
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        --l; --r;
        cout << prefix[r + 1] - prefix[l] << '\n';
    }
}

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

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

long long rectSum(int x1, int y1, int x2, int y2) {
    return pref[x2 + 1][y2 + 1]
         - pref[x1][y2 + 1]
         - pref[x2 + 1][y1]
         + pref[x1][y1];
}

def build_prefix(a):
    prefix = [0] * (len(a) + 1)
    for i, value in enumerate(a):
        prefix[i + 1] = prefix[i] + value
    return prefix


def range_sum(prefix, left, right):
    return prefix[right + 1] - prefix[left]

8. Giải thích code

8.1. Vì sao prefix có kích thước n+1?

prefix[0]=0 là tổng của 0 phần tử, giúp mọi truy vấn dùng chung một công thức.

8.2. Vì sao ghi vào prefix[i+1]?

prefix[i+1] là tổng của i+1 phần tử đầu, tức đoạn a[0..i].

8.3. Vì sao query là prefix[R+1]-prefix[L]?

Tổng từ 0 đến R trừ tổng từ 0 đến L−1 sẽ còn đúng đoạn L đến R.

8.4. Vì sao cần long long?

8.5. Prefix Sum có update tốt không?

Không. Một thay đổi ở a[i] làm thay đổi toàn bộ prefix phía sau. Khi có nhiều update, dùng Fenwick Tree hoặc Segment Tree.

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

• Nhầm giữa prefix kích thước n và n+1.
• Trừ sai: dùng prefix[R]-prefix[L].
• Quên đổi chỉ số 1-based sang 0-based.
• Dùng int cho tổng lớn.
• Quên cộng lại phần giao trong 2D.
• Nhầm đoạn đóng [L,R] với đoạn nửa mở [L,R).
• Dùng Prefix Sum khi có nhiều update.

10. Quiz và bài tập