Prefix sum là gì, và nó tăng tốc các truy vấn khoảng như thế nào?

Question

Accepted Answer

Một mảng **prefix sum** (tổng tiền tố) lưu các tổng tích lũy để bất kỳ **tổng khoảng** nào cũng có thể được trả lời trong **O(1)** sau khi tiền xử lý O(n) — thay vì O(n) mỗi truy vấn.

## Ý tưởng

Gọi `prefix[i]` là tổng của `i` phần tử đầu tiên. Khi đó tổng của `arr[l..r]` là `prefix[r+1] - prefix[l]`.

## Ví dụ

```python
def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i, x in enumerate(arr):
        prefix[i + 1] = prefix[i] + x   # tổng chạy
    return prefix

def range_sum(prefix, l, r):            # bao gồm cả l..r
    return prefix[r + 1] - prefix[l]    # O(1)

p = build_prefix([2, 4, 1, 3, 5])
range_sum(p, 1, 3)                      # 4+1+3 -> 8
```

## Truy vết

```text
arr    = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
```

## Độ phức tạp

- **Xây dựng:** O(n). **Truy vấn:** O(1). **Bộ nhớ:** O(n).

## Khi nào dùng / những cạm bẫy

Lý tưởng cho **nhiều truy vấn tổng khoảng** trên dữ liệu tĩnh. Các biến thể: prefix sum 2D cho tổng ma trận con, prefix XOR, và mảng hiệu (difference array) cho cập nhật khoảng. Nếu mảng thay đổi thường xuyên, hãy dùng Fenwick/segment tree thay thế. Cẩn thận với độ lệch chỉ số (kích thước n+1).

## Tại sao điều này quan trọng

Prefix sum biến các truy vấn khoảng O(n) lặp lại thành các phép tra cứu O(1) — một thắng lợi lớn khi truy vấn diễn ra thường xuyên.

Mô thức tính-trước-một-lần, trả-lời-nhanh khái quát hóa cho nhiều tác vụ xử lý dữ liệu.

Đây là một thành phần chủ lực trong lập trình thi đấu và một khối xây dựng phổ biến trong phân tích dữ liệu (analytics).