Tiền xử lý tính sẵn tổng từ đầu mảng đến mọi vị trí i. Lưu vào mảng P. Khi cần tính tổng đoạn [L, R], chỉ việc lấy tổng đến R trừ đi phần thừa trước L (tổng đến L-1).
Khi có nhiều truy vấn hỏi tổng/XOR/nhân của một đoạn con trên mảng, và mảng đó không bị thay đổi giá trị (tĩnh) trong suốt quá trình truy vấn. Dữ liệu thường cỡ N, Q ≤ 106.
Mạnh: Cực kỳ dễ cài đặt, truy vấn O(1) tối ưu tuyệt đối.
Yếu: Nếu mảng bị cập nhật (ví dụ: đổi a3 = 5), ta phải tính lại toàn bộ mảng P mất O(N).
| Kỹ thuật | Khởi tạo | Truy vấn đoạn | Cập nhật 1 điểm | Độ khó cài | Khi nào ưu tiên? |
|---|---|---|---|---|---|
| Vòng lặp ngây thơ | O(1) | O(N) | O(1) | Rất dễ | Mảng nhỏ, truy vấn cực ít. |
| Mảng Tiền Tố (Bài này) | O(N) | O(1) | O(N) | Dễ | Mảng tĩnh (không cập nhật), truy vấn nhiều. |
| Fenwick Tree (BIT) | O(N) | O(log N) | O(log N) | Vừa | Có cập nhật điểm, chỉ cần tính tổng đoạn. |
| Segment Tree | O(N) | O(log N) | O(log N) | Khó | Truy vấn phức tạp (Max/Min), cập nhật cả đoạn. |
Cho một mảng số nguyên a gồm N phần tử đánh số từ 1 đến N. Có Q câu hỏi (truy vấn), mỗi câu cho hai số L và R, yêu cầu in ra tổng các phần tử từ aL đến aR.
Cách ngây thơ: Với mỗi truy vấn, dùng một vòng lặp for (i = L → R) cộng dồn lại. Nếu N = 105 và Q = 105, trong trường hợp xấu nhất (L=1, R=N), mỗi truy vấn mất O(N) phép tính. Tổng số phép tính là Q × N = 1010. Máy tính chấm thi thường chạy ~108 phép tính/giây, nên cách này sẽ quá thời gian (Time Limit Exceeded).
Ý tưởng cứu vãn: Ta cần một cách nào đó để tính tổng trong O(1). Nếu ta biết trước số tiền của mình vào cuối mỗi ngày, ta có thể dễ dàng biết được từ ngày L đến ngày R mình đã kiếm được bao nhiêu, bằng cách lấy (Tổng tài sản ngày R) trừ đi (Tổng tài sản ngày L-1).
Ta định nghĩa một mảng mới P gọi là mảng tổng tiền tố. Trong đó Pi lưu tổng của các phần tử từ vị trí 1 đến vị trí i.
Pi = a1 + a2 + ... + ai
Để xây dựng mảng P nhanh chóng trong O(N), thay vì lặp lại từ đầu, ta tận dụng kết quả của bước trước:
Pi = Pi-1 + ai
Bây giờ, muốn tính tổng đoạn [L, R] tức là aL + aL+1 + ... + aR, ta nhận thấy:
PR = a1 + ... + aL-1 + aL + ... + aRPL-1 = a1 + ... + aL-1Rõ ràng, lấy phương trình trên trừ phương trình dưới, phần a1 đến aL-1 triệt tiêu lẫn nhau, ta còn lại đúng phần cần tìm! Do đó:
Vì sao cần P0 = 0 ? Nếu L = 1 (tính tổng từ đầu mảng), công thức yêu cầu ta gọi P0. Để công thức luôn đúng mà không cần viết lệnh if (L == 1), ta khởi tạo sẵn P0 = 0.
long long P[7]; P[0] = 0; for (int i = 1; i <= 6; i++) { P[i] = P[i - 1] + a[i]; }
long long query(int L, int R) { long long sumR = P[R]; long long sumL_minus_1 = P[L - 1]; long long ans = sumR - sumL_minus_1; return ans; }
P có kích thước lớn hơn số lượng phần tử một chút (vd: N + 5). Đảm bảo kiểu dữ liệu đủ lớn (64-bit integer, ví dụ long long trong C++) để tránh tràn số khi cộng dồn.P[0] = 0. Bước này thiết lập mốc biên quan trọng.i chạy từ 1 đến N.P[i] = P[i-1] + a[i]. Trạng thái hiện tại lấy trực tiếp từ trạng thái ngay sát trước cộng thêm phần tử mới.L, R nhận được, in ra kết quả của phép toán P[R] - P[L - 1]. Phép toán này chạy độc lập không dùng vòng lặp, nên độ phức tạp là O(1).
#include <iostream>
#include <vector>
using namespace std;
int main() {
// Tối ưu I/O để đọc/ghi nhanh
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// Khởi tạo mảng P kích thước n+1, gán sẵn 0
vector<long long> p(n + 1, 0);
p[0] = 0; // Tường minh gán biên
// Dựng mảng tiền tố O(N)
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] + a[i];
}
// Trả lời các truy vấn O(1) mỗi truy vấn
for (int i = 1; i <= q; i++) {
int l, r;
cin >> l >> r;
// In ra tổng đoạn
cout << p[r] - p[l - 1] << "\n";
}
return 0;
}Nếu mảng có 105 phần tử, mỗi phần tử lớn cỡ 109, thì tổng tối đa có thể lên tới 1014. Con số này vượt qua giới hạn của số nguyên 32-bit (chỉ lưu được cỡ ~2×109).
long long (trong C++) hoặc long (trong Java).Nhiều bạn quen đọc mảng từ a[0] đến a[N-1]. Khi truy vấn đoạn [0, R], công thức trở thành P[R] - P[-1], gây ra lỗi truy cập ngoài biên (Out of bounds/Segmentation fault).
a[1] đến a[N]). Khởi tạo mảng P có cỡ N+1 và gán P[0] = 0.10 bài toán bạn đang tìm hiểu thực chất dẫn chúng ta đến một kỹ thuật song sinh với Mảng Tiền Tố: Mảng Hiệu (Difference Array). Nếu Tiền Tố giúp truy vấn tổng đoạn nhanh trên mảng tĩnh, thì Mảng Hiệu giúp cập nhật cộng đoạn nhanh, sau đó mới truy xuất tĩnh.
v vào đoạn [L, R] của mảng A, ta xét mảng hiệu D và chỉ cần thực hiện 2 phép toán O(1): DL += v và DR+1 -= v.
Đây là áp dụng trực tiếp nhất của Mảng Hiệu. Cứ mỗi thao tác cập nhật/đoạn phủ [L, R], ta cắm 2 "cột mốc" ở hai đầu đoạn.
A, ta cộng vào mảng D. Quét một vòng từ trái sang phải để tính tổng tiền tố của D, ta sẽ khôi phục được mảng A hoàn chỉnh. Các bài toán hỏi độ phủ thực chất là cộng v = 1.
Sau khi dùng mảng hiệu để tạo mảng gốc siêu tốc, ta có thể áp dụng thuật toán khác trên mảng kết quả.
D để cập nhật O(1). Tiền tố hóa D để ra A. Sau đó dựng mảng tiền tố P của A để trả lời truy vấn O(1). Sự kết hợp hoàn hảo!
D. Sau khi có A, ta duyệt mảng 1 lần nữa để đếm các phần tử ≥ v, chia hết cho 3, hoặc có độ phủ là số nguyên tố. Không hề phức tạp hơn, chỉ thêm 1 bước O(N).
2 × N (nếu đáy kín). Nhưng chu vi DỌC thì sao? Chiều dài đường viền dọc lộ ra giữa cột i và cột i-1 chính xác là |Ai - Ai-1|.Ai - Ai-1 vốn chính là Di! Vậy chu vi viền dọc chỉ đơn giản là tổng các giá trị tuyệt đối |Di|. Ta không cần dựng mảng A!
B, ta nhận thấy: Mỗi lần cộng 1 vào [L, R], trên mảng hiệu chỉ sinh ra đúng 1 dấu +1 và 1 dấu -1.B, ta lập mảng hiệu D của B. Số thao tác tối thiểu chính là tổng của tất cả các phần tử dương trong D!
d vào liên tục.