Array Preprocessing

📈 Prefix Max / Prefix Min

Tiền xử lý giá trị lớn nhất và nhỏ nhất trên mọi đoạn đầu của mảng để trả lời nhanh, kiểm tra điều kiện, tối ưu bài toán chia đoạn và kết hợp với suffix max/min.

BuildO(n)
Query prefixO(1)
MemoryO(n)
Static arrayPhù hợp mảng không đổi
Mục tiêuĐặt vấn đềÝ tưởngMô phỏngỨng dụngPhân tíchCode mẫuGiải thích codeLỗi thường gặpQuiz

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

Cần hiểu

  • Ý nghĩa của prefixMax[i] và prefixMin[i].
  • Công thức chuyển trạng thái từ vị trí i−1 sang i.
  • Cách trả lời nhanh max/min trên đoạn đầu [0,i].
  • Cách kết hợp prefix với suffix.
  • Giới hạn của prefix max/min khi truy vấn đoạn bất kỳ.

Khi nào dùng?

  • Mảng tĩnh, nhiều lần hỏi max/min trên đoạn đầu.
  • Cần kiểm tra điều kiện ở mọi vị trí.
  • Chia mảng thành phần trái và phần phải.
  • Tìm phần tử trội nhất trước vị trí i.
  • Tối ưu các bài một lần duyệt.

1. Đặt vấn đề

Bài toán mở đầu.
Cho mảng a[0..n-1]. Có nhiều truy vấn dạng:
  • Giá trị lớn nhất trong đoạn [0,i] là bao nhiêu?
  • Giá trị nhỏ nhất trong đoạn [0,i] là bao nhiêu?
  • Tại vị trí i, bên trái đã từng xuất hiện phần tử lớn hơn a[i] chưa?
  • Nếu chia mảng sau vị trí i, max bên trái và min bên phải là bao nhiêu?

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

Với mỗi truy vấn i, duyệt lại từ đầu mảng đến i để tìm max/min.

Cách làmMỗi truy vấnq truy vấnĐánh giá
Duyệt lại [0,i]O(i+1)Có thể O(nq)Dễ chậm khi q lớn
Tiền xử lý prefix max/minO(1)O(n+q)Đơn giản và rất nhanh

1.2. Quan sát quan trọng

Để biết max trên [0,i], ta chỉ cần so sánh max của đoạn trước với phần tử mới.

prefixMax[i] = max(prefixMax[i−1], a[i])
prefixMin[i] = min(prefixMin[i−1], a[i])
Kết luận: sau một lần duyệt O(n), mọi truy vấn max/min trên đoạn đầu trở thành O(1).

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

Prefix Max

prefixMax[i] là giá trị lớn nhất trong đoạn a[0..i].

prefixMax[0] = a[0]
prefixMax[i] = max(prefixMax[i−1], a[i])

Prefix Min

prefixMin[i] là giá trị nhỏ nhất trong đoạn a[0..i].

prefixMin[0] = a[0]
prefixMin[i] = min(prefixMin[i−1], a[i])
Không giống Prefix Sum: từ hai giá trị prefix max không thể suy ra max trên đoạn bất kỳ [L,R]. Muốn RMQ đoạn bất kỳ cần Sparse Table hoặc Segment Tree.

3. Mô phỏng xây Prefix Max / Min

Mảng a

prefixMax

prefixMin

Nhấn “Bước tiếp” để xây dần hai mảng prefix.

4. Ứng dụng quan trọng

Kiểm tra kỷ lục mới

a[i] là giá trị lớn nhất mới nếu a[i] > prefixMax[i−1].

Chia mảng trái/phải

Kết hợp prefixMax[i] với suffixMin[i+1].

Lợi nhuận lớn nhất

Dùng a[i] − prefixMin[i−1] để mô phỏng mua trước, bán sau.

Phần tử trội

Kiểm tra phần tử có lớn hơn toàn bộ phần tử bên trái.

Tiền xử lý điều kiện

Đánh dấu nhanh những vị trí hợp lệ.

Kết hợp hai chiều

Prefix từ trái sang phải, suffix từ phải sang trái.

4.1. Mô phỏng chia mảng

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

Thành phầnThời gianBộ nhớGhi chú
Xây prefixMaxO(n)O(n)Mỗi phần tử xử lý một lần.
Xây prefixMinO(n)O(n)Tương tự prefixMax.
Query max/min [0,i]O(1)Không thêmLấy trực tiếp từ mảng prefix.
Chỉ cần kết quả cuốiO(n)O(1)Dùng biến chạy.
Update phần tửKhông phù hợp—Một update có thể làm đổi toàn bộ phần sau.

6. Code mẫu

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

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

    int n;
    cin >> n;

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

    vector<long long> prefixMax(n);
    vector<long long> prefixMin(n);

    prefixMax[0] = a[0];
    prefixMin[0] = a[0];

    for (int i = 1; i < n; i++) {
        prefixMax[i] = max(prefixMax[i - 1], a[i]);
        prefixMin[i] = min(prefixMin[i - 1], a[i]);
    }
}
vector<long long> prefixMax(n), suffixMin(n);

prefixMax[0] = a[0];
for (int i = 1; i < n; i++)
    prefixMax[i] = max(prefixMax[i - 1], a[i]);

suffixMin[n - 1] = a[n - 1];
for (int i = n - 2; i >= 0; i--)
    suffixMin[i] = min(suffixMin[i + 1], a[i]);

for (int i = 0; i + 1 < n; i++) {
    if (prefixMax[i] < suffixMin[i + 1])
        cout << i << '\n';
}
def build_prefix_max_min(a):
    n = len(a)
    prefix_max = [0] * n
    prefix_min = [0] * n

    prefix_max[0] = a[0]
    prefix_min[0] = a[0]

    for i in range(1, n):
        prefix_max[i] = max(prefix_max[i - 1], a[i])
        prefix_min[i] = min(prefix_min[i - 1], a[i])

    return prefix_max, prefix_min

7. Giải thích code

7.1. Vì sao khởi tạo từ a[0]?

Đoạn đầu tiên chỉ có một phần tử, nên max và min đều bằng a[0].

7.2. Vì sao trạng thái i chỉ phụ thuộc i−1?

Đoạn [0,i] được tạo từ đoạn [0,i−1] cộng thêm a[i].

7.3. Vì sao không cần vòng lặp lồng nhau?

prefixMax[i−1] đã lưu kết quả tốt nhất của toàn bộ phần trước.

7.4. Khi nào chỉ dùng một biến?

Nếu chỉ cần max/min của toàn mảng, không cần lưu cả mảng prefix.

7.5. Vì sao không truy vấn được max [L,R]?

Prefix Sum có phép trừ. Max/min không có phép nghịch đảo tương ứng, nên không thể lấy hai prefix để loại phần bên trái.

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

  • Khởi tạo prefix bằng 0, sai khi toàn bộ mảng âm.
  • Truy cập prefix[i−1] khi i = 0.
  • Nhầm prefix max với max trên đoạn bất kỳ.
  • Dùng prefix max/min cho dữ liệu có nhiều update.
  • Ở bài chia mảng, dùng nhầm suffixMin[i] thay vì suffixMin[i+1].

9. Quiz và bài tập

Câu 1. prefixMax[i] là gì?
Câu 2. Công thức đúng?
Câu 3. Vì sao prefix max không trả lời trực tiếp max [L,R]?

📘 Cơ bản

  1. In prefix max/min.
  2. Đếm số lần xuất hiện kỷ lục mới.
  3. Tìm vị trí đầu tiên prefix max ≥ K.

📗 Trung bình

  1. Best time to buy and sell stock.
  2. Đếm phần tử lớn hơn mọi phần tử bên trái.
  3. Chia mảng sao cho max trái < min phải.

📙 Nâng cao

  1. Kết hợp prefix max với binary search.
  2. Maximum subarray crossing a fixed point.
  3. Bài loại một phần tử.

🐉 HSG

  1. Tối ưu DP bằng prefix best.
  2. Kết hợp monotonic stack.
  3. Offline query theo ngưỡng.
⬅️ Quay lại Roadmap