Khái Niệm Về Kỹ Thuật Doubling

Doubling (hay còn gọi là Binary Lifting) là một kỹ thuật tối ưu hóa thuật toán dựa trên nguyên lý nhảy cóc theo lũy thừa của 2. Thay vì duyệt tuần tự từng bước một với độ phức tạp O(n), phương pháp này cho phép thực hiện các bước nhảy có độ dài 2^k, giúp giảm độ phức tạp thời gian xuống còn O(log n). Đây là nền tảng của nhiều thuật toán quan trọng, bao gồm cả bài toán tìm tổ tiên chung gần nhất (LCA).

Cấu Trúc Sparse Table (ST Table)

Sparse Table là một cấu trúc dữ liệu tĩnh, thường được sử dụng để truy vấn các giá trị trên một đoạn mảng mà không có thao tác cập nhật. Với chi phí tiền xử lý O(n log n), ST Table hỗ trợ truy vấn các phép toán có tính chất lũy đẳng (idempotent) như tìm cực đại, cực tiểu, hoặc UCLN trên một đoạn [L, R] với độ phức tạp O(1).

Đối với các phép toán không có tính lũy đẳng như tổng hay tích, ST Table vẫn có thể áp dụng nhưng độ phức tạp truy vấn sẽ là O(log n), tuy nhiên trường hợp này ít phổ biến hơn.

Dưới đây là cách triển khai cơ bản cho việc xây dựng và truy vấn ST Table:

const int MAXN = 100005;
const int LOGN = 20;
int arr[MAXN], logs[MAXN];
int sparse[MAXN][LOGN];
int n;

void preprocess() {
    logs[1] = 0;
    for (int i = 2; i <= n; i++)
        logs[i] = logs[i / 2] + 1;

    for (int i = 0; i < n; i++)
        sparse[i][0] = arr[i];

    for (int j = 1; j < LOGN; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            sparse[i][j] = max(sparse[i][j - 1], 
                               sparse[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int L, int R) {
    int j = logs[R - L + 1];
    return max(sparse[L][j], sparse[R - (1 << j) + 1][j]);
}

Ứng Dụng Trong Nhân Ma Trận Nhanh

Một dạng khác của kỹ thuật doubling là phép lũy thừa ma trận nhanh. Khi mô hình hóa bài toán trên đồ thị bằng ma trận kề, việc tìm đường đi ngắn nhất với số cạnh cố định hoặc đếm số đường đi có thể quy về phép nhân ma trận. Phép lũy thừa ma trận với số mũ lớn thực chất cũng là quá trình nhân đôi liên tiếp.

Ví dụ dưới đây giải quyết bài toán tìm đường đi ngắn nhất giữa hai đỉnh với đúng k bước di chuyển trên đồ thị vô hướng có trọng số:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int SZ = 105;

struct Matrix {
    ll val[SZ][SZ];
    int size;
    Matrix(int s) : size(s) {
        for(int i=0; i<s; ++i)
            for(int j=0; j<s; ++j) val[i][j] = INF;
    }
};

Matrix multiply(const Matrix &A, const Matrix &B) {
    Matrix C(A.size);
    for (int i = 0; i < A.size; i++) {
        for (int k = 0; k < A.size; k++) {
            if (A.val[i][k] == INF) continue;
            for (int j = 0; j < A.size; j++) {
                C.val[i][j] = min(C.val[i][j], A.val[i][k] + B.val[k][j]);
            }
        }
    }
    return C;
}

Matrix power(Matrix base, ll exp) {
    Matrix res(base.size);
    for(int i=0; i<base.size; ++i) res.val[i][i] = 0;
    while (exp > 0) {
        if (exp & 1) res = multiply(res, base);
        base = multiply(base, base);
        exp >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    ll steps, m, startNode, endNode;
    cin >> steps >> m >> startNode >> endNode;
    
    map<ll, int> idMap;
    int cnt = 0;
    auto getId = [&](ll x) {
        if (!idMap.count(x)) idMap[x] = cnt++;
        return idMap[x];
    };

    Matrix base(SZ);
    // Giả sử kích thước ma trận đủ lớn hoặc dynamic
    // Ở đây minh họa logic chính
    
    for (int i = 0; i < m; i++) {
        ll w, u, v;
        cin >> w >> u >> v;
        int uid = getId(u), vid = getId(v);
        base.val[uid][vid] = min(base.val[uid][vid], w);
        base.val[vid][uid] = min(base.val[vid][uid], w);
    }
    
    // Lưu ý: Cần điều chỉnh kích thước ma trận thực tế theo cnt
    // Đoạn code này minh họa logic nhân ma trận min-plus
    return 0;
}

Kết Hợp Tìm Nhị Phân Và ST Table

Khi các giá trị trên đoạn mảng thỏa mãn tính đơn điệu, ta có thể kết hợp ST Table với tìm kiếm nhị phân. Ví dụ, với phép toán bitwise AND, giá trị trên một đoạn mở rộng dần sẽ không tăng. Do đó, với một điểm bắt đầu cố định, ta có thể tìm điểm kết thúc xa nhất sao cho giá trị AND của đoạn đó lớn hơn hoặc bằng một ngưỡng K cho trước.

Quy trình thực hiện gồm xây dựng ST Table cho phép AND, sau đó với mỗi truy vấn, thực hiện binary search trên đáp án:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 200005;
const int LOGN = 20;

ll arr[MAXN], st[MAXN][LOGN], logs[MAXN];
int n;

ll getAND(int L, int R) {
    int j = logs[R - L + 1];
    return (st[L][j] & st[R - (1 << j) + 1][j]);
}

void solve() {
    cin >> n;
    logs[1] = 0;
    for (int i = 2; i <= n; i++) logs[i] = logs[i / 2] + 1;

    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        st[i][0] = arr[i];
    }

    for (int j = 1; j < LOGN; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = st[i][j - 1] & st[i + (1 << (j - 1))][j - 1];
        }
    }

    int q; cin >> q;
    while (q--) {
        int x; ll k;
        cin >> x >> k;
        int low = x, high = n, ans = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (getAND(x, mid) >= k) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        cout << ans << " ";
    }
    cout << "\n";
}

Tiền Xử Lý Phức Tạp Kết Hợp Doubling

Trong một số bài toán nâng cao, trạng thái để xây dựng ST Table không có sẵn mà cần được tính toán qua các bước tiền xử lý phức tạp như phân tích thừa số nguyên tố hoặc sử dụng kỹ thuật hai con trỏ (two pointers). Mục tiêu là xác định vị trí tiếp theo thỏa mãn điều kiện nào đó, sau đó dùng doubling để nhảy nhanh đến đích.

Ví dụ, với mỗi vị trí i, ta tìm vị trí j nhỏ nhất sao cho đoạn [i, j] thỏa mãn điều kiện về ước chung. Sau đó, st[i][0] sẽ lưu trữ giá trị j này. Các lớp st[i][k] tiếp theo sẽ lưu vị trí nhảy sau 2^k lần chuyển tiếp.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 100005;
const int LOGN = 20;

ll arr[MAXN];
vector<ll> factors[MAXN];
int nxt[MAXN][LOGN];
int cntPrime[MAXN];
int n, q;

void precompute() {
    for (int i = 1; i <= n; i++) {
        ll tmp = arr[i];
        for (ll j = 2; j * j <= tmp; j++) {
            if (tmp % j == 0) {
                factors[i].push_back(j);
                while (tmp % j == 0) tmp /= j;
            }
        }
        if (tmp > 1) factors[i].push_back(tmp);
    }

    int l = 1, r = 1, distinctCount = 0;
    memset(cntPrime, 0, sizeof(cntPrime));

    while (l <= n) {
        while (r <= n) {
            bool canExtend = true;
            for (ll p : factors[r]) {
                if (cntPrime[p] > 0) {
                    canExtend = false;
                    break;
                }
            }
            if (!canExtend) break;
            
            for (ll p : factors[r]) {
                cntPrime[p]++;
            }
            r++;
        }
        nxt[l][0] = r; 
        // Di chuyển con trỏ trái
        for (ll p : factors[l]) {
            cntPrime[p]--;
        }
        l++;
    }

    for (int j = 1; j < LOGN; j++) {
        for (int i = 1; i <= n; i++) {
            if (nxt[i][j - 1] <= n)
                nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
            else
                nxt[i][j] = n + 1;
        }
    }
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    precompute();

    while (q--) {
        int l, r;
        cin >> l >> r;
        int steps = 0;
        int curr = l;
        for (int j = LOGN - 1; j >= 0; j--) {
            if (nxt[curr][j] <= r) {
                curr = nxt[curr][j];
                steps += (1 << j);
            }
        }
        cout << steps + 1 << "\n";
    }
    return 0;
}