Mảng cộng dồn (Prefix Sum)

Kỹ thuật Mảng cộng dồn (Prefix Sum) là một trong những kỹ thuật tối ưu hóa quan trọng và phổ biến nhất trong lập trình thi đấu, đặc biệt hữu ích trong các kỳ thi học sinh giỏi Tin học. Kỹ thuật này giúp chuyển đổi các bài toán tính tổng đoạn từ độ phức tạp lớn xuống độ phức tạp cực kỳ tối ưu.

Dưới đây là hướng dẫn chi tiết từ lý thuyết, ví dụ mẫu đến bài tập luyện tập.

1. Lý thuyết cốt lõi về Mảng cộng dồn 1 chiều

Bài toán đặt ra

Cho một mảng A gồm N số nguyên. Bạn nhận được Q truy vấn (queries). Mỗi truy vấn yêu cầu tính tổng các phần tử từ chỉ số L đến chỉ số R (tức là A[L] + A[L+1] + … + A[R]).

  • Cách làm ngây thơ (Brute Force): Với mỗi truy vấn, dùng vòng lặp cộng từ L đến R.

    • Độ phức tạp mỗi truy vấn: O(R – L + 1) \approx O(N).

    • Tổng độ phức tạp cho Q truy vấn: O(Q \times N). Nếu N, Q <= 10^5, chương trình sẽ chạy quá thời gian (TLE).

Ý tưởng của Mảng cộng dồn

Ta tạo một mảng mới gọi là mảng cộng dồn S, trong đó S[i] lưu tổng các phần tử từ đầu mảng đến phần tử thứ i của mảng A.

  • Công thức xây dựng (với chỉ số bắt đầu từ 1):

    S[i] = S[i - 1] + A[i] (với S[0] = 0)

  • Công thức truy vấn tổng đoạn từ L đến R:

    Tổng từ L đến R được tính bằng: S[R] - S[L - 1]

  • Độ phức tạp:

    • Tiền xử lý (xây dựng mảng S): O(N)

    • Trả lời mỗi truy vấn: O(1)

    • Tổng độ phức tạp: O(N + Q), cực kỳ nhanh!

2. Ví dụ mẫu trong Python

Dưới đây là đoạn code chuẩn minh họa cách sử dụng mảng cộng dồn 1 chiều trong Python (sử dụng chỉ số 1-based để dễ hình dung công thức):

Python

 
def solve_prefix_sum():
  # Mảng gốc A (thêm số 0 ở đầu để dễ đồng bộ chỉ số từ 1)
  A = [0, 2, 4, -5, 6, 1, 3]
  n = len(A) - 1

  # Bước 1: Xây dựng mảng cộng dồn S
  S = [0] * (n + 1)
  for i in range(1, n + 1):
    S[i] = S[i - 1] + A[i]

  print("Mảng A:", A[1:])
  print("Mảng S:", S[1:])

  # Bước 2: Trả lời các truy vấn tính tổng đoạn [L, R]
  # Ví dụ các truy vấn:
  # - Tính tổng từ 2 đến 5
  # - Tính tổng từ 1 đến 3
  queries = [(2, 5), (1, 3), (4, 6)]

  for L, R in queries:
    # Công thức cốt lõi: S[R] - S[L-1]
    ans = S[R] - S[L - 1]
    print(f"Tổng từ vị trí {L} đến {R} là: {ans}")


solve_prefix_sum()

3. Bài tập luyện tập

Dưới đây là 2 bài tập từ cơ bản đến nâng cao thường gặp trong các đề thi HSG Tin học lớp 9 để bạn rèn luyện:

Bài tập 1: Đoạn con cân bằng (Cơ bản)

  • Đề bài: Cho một mảng số nguyên A gồm N phần tử (N \le 10^5). Hãy tìm xem có tồn tại một chỉ số k (với 1 < k < N) sao cho tổng các phần tử từ đầu đến k-1 bằng tổng các phần tử từ k+1 đến cuối mảng hay không. Nếu có, hãy in ra chỉ số k đó.

  • Gợi ý giải:

    1. Xây dựng mảng cộng dồn S cho toàn bộ mảng.

    2. Tổng bên trái của k chính là S[k-1].

    3. Tổng bên phải của k chính là S[N] – S[k].

    4. Duyệt qua các giá trị k từ 2 đến N-1 và kiểm tra điều kiện S[k-1] == S[N] – S[k].

Bài tập 2: Kho báu lớn nhất (Nâng cao)

  • Đề bài: Trên một tuyến đường thẳng có N ô đựng kho báu được đánh số từ 1 đến N. Ô thứ i có giá trị kho báu là A[i] (có thể âm do có bẫy). Bạn được phép chọn một đoạn liên tiếp các ô từ L đến R sao cho độ dài của đoạn đó không vượt quá một số nguyên dương K cho trước. Hãy tìm tổng giá trị kho báu lớn nhất có thể thu được.

  • Gợi ý giải:

    1. Sử dụng mảng cộng dồn S để tổng đoạn từ L đến R tính được ngay trong O(1) là S[R] – S[L-1].

    2. Điều kiện độ dài đoạn không vượt quá K nghĩa là R – L + 1 \le K, suy ra R – K \le L-1 < R.

    3. Để tối đa hóa S[R] – S[L-1], với mỗi điểm kết thúc R, ta cần tìm giá trị nhỏ nhất của S[L-1] trong khoảng hợp lệ phía trước. Có thể kết hợp kỹ thuật hàng đợi hai đầu (deque) hoặc cửa sổ trượt để tối ưu hóa việc tìm min trong O(N).

📌 Bạn gặp sự cố khi tải tài liệu?

Nếu không tải được file hoặc phát hiện link lỗi, vui lòng nhấn nút Hỗ trợ phía trên thanh Menu hoặc liên hệ trực tiếp với Ban quản trị để được xử lý nhanh nhất. Cảm ơn các bạn!

Để lại một bình luận