Editorial for qmin: Truy vấn số nhỏ nhất trên dãy số

Hiểu bài toán

Bài toán yêu cầu xử lý Q truy vấn trên một dãy số gồm n phần tử. Với mỗi truy vấn gồm hai chỉ số u và v (u ≤ v), ta cần tìm giá trị nhỏ nhất trong đoạn con từ chỉ số u đến chỉ số v của dãy. Dữ liệu bài toán khá lớn: n lên tới 10^6 và Q lên tới 10^5, do đó các giải thuật quá chậm (như duyệt toàn bộ cho mỗi truy vấn) sẽ không thể thực hiện trong thời gian cho phép.

Các cách tiếp cận

Cách Brute Force (Duyệt toàn bộ)

// Pseudocode for Brute Force
void solve() {
    for (int i = 0; i < Q; i++) {
        int u, v;
        cin >> u >> v;
        int min_val = a[u];
        for (int j = u; j <= v; j++) {
            if (a[j] < min_val) min_val = a[j];
        }
        cout << min_val << " ";
    }
}

• Time Complexity: O(Q * n)
• Space Complexity: O(n)

Với mỗi truy vấn, ta duyệt từ u đến v để tìm số nhỏ nhất. Với Q truy vấn, độ phức tạp tổng cộng là O(Q * n). Với n = 10^6 và Q = 10^5, số phép tính lên tới 10^11, vượt quá giới hạn thời gian (thường là 1 giây tương đương ~10^8 phép tính).

Cách Segment Tree (Cây phân đoạn)

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

const int maxn = 1e6 + 5;
const int INF = 2e9 + 7;
int a[maxn];
int tree[4 * maxn];

void build(int id, int l, int r) {
    if (l == r) {
        tree[id] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * id, l, mid);
    build(2 * id + 1, mid + 1, r);
    tree[id] = min(tree[2 * id], tree[2 * id + 1]);
}

int query(int id, int l, int r, int u, int v) {
    if (u > r || v < l) return INF; // Khoảng cách nhau
    if (u <= l && r <= v) return tree[id]; // Khoảng nằm gọn
    int mid = (l + r) / 2;
    return min(query(2 * id, l, mid, u, v), 
               query(2 * id + 1, mid + 1, r, u, v));
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int u, v; cin >> u >> v;
        cout << query(1, 1, n, u, v) << " ";
    }
    return 0;
}

• Time Complexity: O(n) để xây dựng cây, O(log n) cho mỗi truy vấn. Tổng: O(n + Q log n)
• Space Complexity: O(n)

Segment Tree là cấu trúc cây nhị phân cho phép xử lý các truy vấn trên đoạn (range queries) hiệu quả. Mỗi node trong cây lưu giá trị nhỏ nhất của một đoạn con. Nếu đoạn truy vấn nằm gọn trong một node, ta lấy giá trị trực tiếp. Nếu không, ta chia đôi đoạn và kết quả là giá trị nhỏ nhất của 2 nửa. Với n=10^6, cây có khoảng 4n node, số bước cho mỗi truy vấn là log2(10^6) ≈ 20, tổng thời gian khoảng 210^6 + 10^5 * 20 ≘ 4*10^6, hoàn toàn đáp ứng thời gian.

Cách Sparse Table

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

const int maxn = 1e6 + 5;
const int LOG = 20;
int a[maxn];
int st[maxn][LOG];
int lg[maxn];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // Precompute logarithms
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;

    // Build Sparse Table
    for (int i = 1; i <= n; i++) st[i][0] = a[i];
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1]);
        }
    }

    // Answer queries
    while (q--) {
        int u, v; cin >> u >> v;
        int j = lg[v - u + 1];
        cout << min(st[u][j], st[v - (1 << j) + 1][j]) << " ";
    }
    return 0;
}

• Time Complexity: O(n log n) tiền xử lý, O(1) mỗi truy vấn. Tổng: O(n log n + Q)
• Space Complexity: O(n log n)

Sparse Table cho phép trả lời truy vấn Range Minimum Query (RMQ) trong thời gian O(1) sau khi tiền xử lý O(n log n). Nó dựa trên ý tưởng rằng bất kỳ đoạn nào cũng có thể được bao phủ bởi 2 đoạn con có độ dài là lũy thừa 2 (cùng độ dài, có thể chồng lên nhau). Bảng st[i][j] lưu giá trị nhỏ nhất của đoạn bắt đầu tại i có độ dài 2^j. Tuy nhiên, do chi phí bộ nhớ O(n log n) khá lớn (với n=10^6, log n=20, cần ~80MB), Segment Tree thường được ưu tiên hơn trong các kỳ thi lập trình nếu yêu cầu không quá khắt khe về thời gian truy vấn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán là dạng Range Minimum Query (RMQ) kinh điển.
• Segment Tree là lựa chọn cân bằng tốt giữa độ phức tạp thời gian và bộ nhớ cho bài toán này.
• Đối với các bài toán chỉ yêu cầu tìm min/max và không có update, Sparse Table cho tốc độ truy vấn nhanh nhất (O(1)), nhưng tốn nhiều bộ nhớ hơn.

Lỗi thường gặp

• Lỗi tràn số nguyên (integer overflow): Cần dùng kiểu dữ liệu phù hợp (ví dụ long long) nếu giá trị ai lớn, nhưng với |ai| <= 10^9 thì int (với limit ~2*10^9) vẫn đủ dùng nếu khai báo INF cẩn thận.
• Lỗi chỉ số mảng (Off-by-one error): Các giải thuật cây phân đoạn thường dùng chỉ số 1-based hoặc 0-based, cần thống nhất từ đầu.
• Quên tiền xử lý logarithm cho Sparse Table hoặc khai báo mảng quá nhỏ gây tràn bộ nhớ stack/heap.