Khóa học CTDL và GT

Bài 24.4. Sparse Table và ứng dụng trong LCA

Trong thế giới của Cấu trúc dữ liệu và Giải thuật, việc xử lý các truy vấn trên một đoạn (range queries) là một yêu cầu cực kỳ phổ biến. Từ việc tìm giá trị nhỏ nhất, lớn nhất, tổng, hay thậm chí là tổ tiên chung gần nhất trong cây, chúng ta thường xuyên cần trích xuất thông tin từ một phạm vi nhất định của dữ liệu.

Có nhiều cấu trúc dữ liệu mạnh mẽ cho bài toán này, như Segment Tree hay Fenwick Tree. Tuy nhiên, khi dữ liệu của chúng ta là tĩnh (không thay đổi sau khi khởi tạo), Sparse Table nổi lên như một ứng dụng đặc biệt, cho phép chúng ta trả lời các truy vấn trên đoạn với tốc độ đáng kinh ngạc: O(1)!

Bài viết này sẽ đưa bạn đi sâu vào thế giới của Sparse Table: nó là gì, hoạt động như thế nào, và đặc biệt là cách nó được sử dụng như một "chìa khóa" để giải quyết bài toán tìm Tổ tiên chung gần nhất (LCA) một cách hiệu quả.

Sparse Table là gì?

Sparse Table là một cấu trúc dữ liệu được sử dụng để trả lời các truy vấn trên đoạn trên một mảng tĩnh. Ưu điểm vượt trội của nó là khả năng trả lời truy vấn trong thời gian O(1), đổi lại là thời gian tiền xử lý (preprocessing) O(N log N) và không hỗ trợ cập nhật dữ liệu.

Nó đặc biệt hiệu quả với các toán tử khả mỹ (idempotent operations), tức là các toán tử mà việc áp dụng nó nhiều lần trên cùng một phần tử không làm thay đổi kết quả. Các ví dụ điển hình là:

• Tìm giá trị nhỏ nhất (Range Minimum Query - RMQ)
• Tìm giá trị lớn nhất (Range Maximum Query - RMQ)
• Tìm ước chung lớn nhất (GCD)
• Tìm hợp (union)
• Tìm giao (intersection)

Toán tử như tính tổng thì không khả mỹ (1+1+1 khác 1+1). Sparse Table không tối ưu cho các toán tử không khả mỹ nếu đoạn truy vấn có thể bị chia nhỏ và hợp lại.

Cấu trúc và cách xây dựng

Sparse Table dựa trên ý tưởng chia để trị và quy hoạch động để lưu trữ kết quả của các truy vấn trên các đoạn có độ dài là lũy thừa của 2.

Chúng ta sử dụng một bảng 2 chiều, gọi là ST, với kích thước khoảng N x log N. ST[i][j] sẽ lưu trữ kết quả của toán tử trên đoạn bắt đầu từ chỉ số i và có độ dài 2^j. Tức là đoạn [i, i + 2^j - 1].

• Cơ sở (Base Case): Đối với độ dài 2^0 = 1, ST[i][0] đơn giản là giá trị tại chỉ số i trong mảng gốc. ST[i][0] = arr[i].

• Bước quy hoạch động: Để tính ST[i][j], tức là kết quả trên đoạn [i, i + 2^j - 1], chúng ta chia đoạn này làm hai nửa có độ dài 2^(j-1):

  • Nửa đầu: [i, i + 2^(j-1) - 1]. Kết quả đã được tính và lưu ở ST[i][j-1].
  • Nửa sau: [i + 2^(j-1), i + 2^j - 1]. Đoạn này bắt đầu tại chỉ số i + 2^(j-1). Kết quả đã được tính và lưu ở ST[i + 2^(j-1)][j-1].

  Vậy, ST[i][j] sẽ là kết quả khi áp dụng toán tử trên ST[i][j-1] và ST[i + 2^(j-1)][j-1].

  ST[i][j] = op(ST[i][j-1], ST[i + 2^(j-1)][j-1])

  Ví dụ với toán tử tìm giá trị nhỏ nhất (min): ST[i][j] = min(ST[i][j-1], ST[i + (1 << (j-1))][j-1]) (Ở đây 1 << (j-1) chính là 2^(j-1))

Việc xây dựng bảng ST được thực hiện bằng cách lặp j (từ 1 đến log N) và sau đó lặp i (từ 0 đến N - 2^j) để điền vào bảng.

Để tính log N một cách hiệu quả cho mỗi độ dài đoạn, chúng ta có thể tiền xử lý một bảng logarithm cơ số 2. log_2[k] sẽ lưu floor(log2(k)). Bảng này có thể được tính trong O(N): log_2[k] = log_2[k/2] + 1.

Thời gian tiền xử lý để xây dựng Sparse Table là O(N log N) vì chúng ta có log N cột (cho j) và khoảng N hàng (cho i) trong bảng ST, mỗi ô mất O(1) để tính.

Truy vấn

Giả sử chúng ta muốn trả lời truy vấn cho đoạn [L, R] (bao gồm cả L và R). Độ dài của đoạn là len = R - L + 1.

Để trả lời truy vấn bằng Sparse Table, chúng ta cần tìm một hoặc hai đoạn có độ dài là lũy thừa của 2 để phủ lấp toàn bộ đoạn [L, R]. Vì Sparse Table hoạt động tốt nhất với các toán tử khả mỹ, chúng ta có thể sử dụng hai đoạn con có độ dài 2^k mà chúng có thể chồng lấn nhau, miễn là chúng cùng nhau bao phủ đoạn [L, R].

Chúng ta tìm số nguyên lớn nhất k sao cho 2^k <= len. Giá trị k này chính là floor(log2(len)). Chúng ta có thể lấy giá trị k từ bảng log_2 đã tiền xử lý: k = log_2[len].

Hai đoạn con có độ dài 2^k để phủ lấp [L, R] là:

1. Đoạn bắt đầu từ L, có độ dài 2^k: [L, L + 2^k - 1]. Kết quả cho đoạn này được lưu tại ST[L][k].
2. Đoạn kết thúc tại R, có độ dài 2^k: [R - 2^k + 1, R]. Đoạn này bắt đầu tại chỉ số R - 2^k + 1. Kết quả cho đoạn này được lưu tại ST[R - 2^k + 1][k].

Vì toán tử là khả mỹ, kết quả trên đoạn [L, R] chính là kết quả áp dụng toán tử lên ST[L][k] và ST[R - 2^k + 1][k].

query(L, R) = op(ST[L][k], ST[R - 2^k + 1][k]) với k = log_2[R - L + 1]

Thời gian trả lời một truy vấn là O(1) vì chúng ta chỉ cần vài phép tính đơn giản và tra bảng log_2 (O(1)) và ST (O(1)).

Ví dụ minh họa: Range Minimum Query (RMQ)

Bài toán: Cho một mảng A gồm N số nguyên. Trả lời truy vấn: tìm giá trị nhỏ nhất trong đoạn A[L..R].

Giả sử mảng A = [7, 2, 3, 0, 5, 10, 8] (N = 7). log2(7) ≈ 2.8, nên giá trị k tối đa cần xét là floor(log2(N)) = 2. Tuy nhiên, để an toàn, chúng ta có thể dùng ceil(log2(N)) hoặc một hằng số đủ lớn, ví dụ MAX_LOG = 18 vì 2^18 > 2e5. Mảng A có 7 phần tử, chỉ số từ 0 đến 6.

Tiền xử lý (Build ST):

• Bảng log_2: log_2[1] = 0 log_2[2] = 1 log_2[3] = log_2[1] + 1 = 1 log_2[4] = log_2[2] + 1 = 2 log_2[5] = log_2[2] + 1 = 2 log_2[6] = log_2[3] + 1 = 2 log_2[7] = log_2[3] + 1 = 2

• Bảng ST (lưu giá trị min): Kích thước ví dụ ST[7][3] (7 hàng, 3 cột 0..2).

  • j = 0 (độ dài 2^0 = 1): ST[i][0] = A[i] ST[0][0] = 7 ST[1][0] = 2 ST[2][0] = 3 ST[3][0] = 0 ST[4][0] = 5 ST[5][0] = 10 ST[6][0] = 8

  • j = 1 (độ dài 2^1 = 2): ST[i][1] = min(ST[i][0], ST[i+1][0]) ST[0][1] = min(ST[0][0], ST[1][0]) = min(7, 2) = 2 (đoạn [7, 2]) ST[1][1] = min(ST[1][0], ST[2][0]) = min(2, 3) = 2 (đoạn [2, 3]) ST[2][1] = min(ST[2][0], ST[3][0]) = min(3, 0) = 0 (đoạn [3, 0]) ST[3][1] = min(ST[3][0], ST[4][0]) = min(0, 5) = 0 (đoạn [0, 5]) ST[4][1] = min(ST[4][0], ST[5][0]) = min(5, 10) = 5 (đoạn [5, 10]) ST[5][1] = min(ST[5][0], ST[6][0]) = min(10, 8) = 8 (đoạn [10, 8])

  • j = 2 (độ dài 2^2 = 4): ST[i][2] = min(ST[i][1], ST[i+2][1]) ST[0][2] = min(ST[0][1], ST[2][1]) = min(2, 0) = 0 (đoạn [7, 2, 3, 0]) ST[1][2] = min(ST[1][1], ST[3][1]) = min(2, 0) = 0 (đoạn [2, 3, 0, 5]) ST[2][2] = min(ST[2][1], ST[4][1]) = min(0, 5) = 0 (đoạn [3, 0, 5, 10]) ST[3][2] = min(ST[3][1], ST[5][1]) = min(0, 8) = 0 (đoạn [0, 5, 10, 8])

Truy vấn: Tìm min trong đoạn A[1..5] (L=1, R=5). Đoạn: [2, 3, 0, 5, 10]. Độ dài len = R - L + 1 = 5 - 1 + 1 = 5. k = log_2[5] = 2. 2^k = 2^2 = 4. Hai đoạn con độ dài 4:

1. Bắt đầu từ L=1: [1, 1 + 4 - 1] = [1, 4]. Kết quả tại ST[1][2].
2. Kết thúc tại R=5: [5 - 4 + 1, 5] = [2, 5]. Kết quả tại ST[2][2].

Kết quả truy vấn: min(ST[1][2], ST[2][2]) = min(0, 0) = 0. Kiểm tra lại mảng A[1..5] = [2, 3, 0, 5, 10], giá trị nhỏ nhất đúng là 0.

C++ Code Minh họa cho RMQ

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

const int MAXN = 200005; // Kích thước mảng tối đa
const int MAX_LOG = 18; // log2(MAXN) khoảng 18

int arr[MAXN];
int st[MAXN][MAX_LOG];
int log_table[MAXN];

// Hàm tiền xử lý Sparse Table
void build_sparse_table(int n) {
    // Tiền xử lý bảng log_2
    log_table[1] = 0;
    for (int i = 2; i <= n; i++) {
        log_table[i] = log_table[i / 2] + 1;
    }

    // Khởi tạo cột j=0
    for (int i = 0; i < n; i++) {
        st[i][0] = arr[i];
    }

    // Xây dựng các cột j > 0
    for (int j = 1; j < MAX_LOG; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            st[i][j] = std::min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

// Hàm truy vấn RMQ trên đoạn [l, r] (0-based index)
int query_sparse_table(int l, int r) {
    int len = r - l + 1;
    int k = log_table[len];
    return std::min(st[l][k], st[r - (1 << k) + 1][k]);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n; // Kích thước mảng
    std::cout << "Nhap so phan tu cua mang: ";
    std::cin >> n;

    std::cout << "Nhap cac phan tu cua mang:\n";
    for (int i = 0; i < n; i++) {
        std::cin >> arr[i];
    }

    build_sparse_table(n);

    int q; // Số lượng truy vấn
    std::cout << "Nhap so luong truy van: ";
    std::cin >> q;

    std::cout << "Nhap cac truy van (l, r) (0-based index):\n";
    for (int i = 0; i < q; i++) {
        int l, r;
        std::cin >> l >> r;
        if (l > r || l < 0 || r >= n) {
             std::cout << "Khoang truy van khong hop le!\n";
        } else {
            std::cout << "Gia tri nho nhat trong doan [" << l << ", " << r << "] la: "
                       << query_sparse_table(l, r) << "\n";
        }
    }

    return 0;
}

Giải thích Code RMQ:

1. Constants MAXN, MAX_LOG: Đặt kích thước tối đa cho mảng và số cột tối đa trong bảng Sparse Table. MAX_LOG là giá trị k lớn nhất sao cho 2^k <= MAXN.
2. Arrays arr, st, log_table:
   • arr: Mảng gốc chứa dữ liệu.
   • st[i][j]: Bảng Sparse Table lưu kết quả min trên đoạn [i, i + 2^j - 1].
   • log_table[k]: Lưu floor(log2(k)).
3. build_sparse_table(int n):
   • Tính log_table: Lặp từ 2 đến n, log_table[i] dựa trên log_table[i/2]. Đây là cách hiệu quả O(N) để tính log2 cho mọi số từ 1 đến N.
   • Khởi tạo j=0: Cột đầu tiên của st được điền trực tiếp từ mảng arr.
   • Xây dựng các cột j > 0: Vòng lặp ngoài đi từ j=1 đến MAX_LOG-1. Vòng lặp trong đi từ i=0. Điều kiện i + (1 << j) <= n đảm bảo đoạn [i, i + 2^j - 1] không vượt quá kích thước mảng. st[i][j] được tính bằng cách lấy min của hai đoạn con: [i, i + 2^(j-1) - 1] (lưu ở st[i][j-1]) và [i + 2^(j-1), i + 2^j - 1] (lưu ở st[i + (1 << (j - 1))][j - 1]).
4. query_sparse_table(int l, int r):
   • Tính len = r - l + 1.
   • Tìm k = log_table[len]. Đây là lũy thừa lớn nhất của 2 nhỏ hơn hoặc bằng độ dài đoạn.
   • Trả về giá trị nhỏ nhất giữa hai đoạn độ dài 2^k: đoạn bắt đầu từ l (st[l][k]) và đoạn kết thúc tại r (st[r - (1 << k) + 1][k]).
5. main: Đọc kích thước mảng và các phần tử, gọi build_sparse_table. Đọc số lượng truy vấn và các truy vấn, gọi query_sparse_table và in kết quả.

Ứng dụng của Sparse Table: Tìm Tổ Tiên Chung Gần Nhất (LCA)

Một trong những ứng dụng kinh điển và mạnh mẽ của Sparse Table là trong bài toán tìm Tổ tiên chung gần nhất (Lowest Common Ancestor - LCA) trên một cây gốc (rooted tree).

Bài toán LCA: Cho một cây có gốc R, và hai nút bất kỳ u và v. Tìm nút w là tổ tiên chung của cả u và v, và w có độ sâu lớn nhất (tức là gần u và v nhất).

Có nhiều thuật toán để giải quyết bài toán LCA, bao gồm cả phương pháp ngoại tuyến (offline) sử dụng DSU và phương pháp trực tuyến (online) sử dụng Binary Lifting (O(N log N) preproc, O(log N) query) hoặc Segment Tree/Sparse Table trên biến đổi Euler Tour. Phương pháp dùng Sparse Table cho phép truy vấn O(1) sau tiền xử lý O(N log N).

Ý tưởng chính để áp dụng Sparse Table vào LCA là biến đổi bài toán LCA trên cây thành bài toán RMQ trên một mảng tuyến tính. Kỹ thuật biến đổi này được gọi là Euler Tour kết hợp với RMQ trên mảng độ sâu.

Biến đổi bằng Euler Tour

1. Thực hiện Euler Tour (DFS traversal): Duyệt cây bằng DFS. Mỗi khi thăm một nút (lần đầu vào, hoặc quay lại từ nút con), ghi lại ID của nút đó và độ sâu của nó vào hai mảng riêng biệt. Ví dụ: Cây có gốc A, con B, C. B có con D.

         A (độ sâu 0)
        / \
       B(1) C(1)
      /
     D(2)

   Một Euler Tour có thể là: A -> B -> D -> (quay về B) -> B -> (quay về A) -> A -> C -> (quay về A) -> A. Mảng nút trong Euler Tour: [A, B, D, B, A, C, A] Mảng độ sâu tương ứng: [0, 1, 2, 1, 0, 1, 0]

   Ngoài ra, trong quá trình DFS, chúng ta cần ghi lại chỉ số lần xuất hiện đầu tiên của mỗi nút trong mảng Euler Tour. first_occurrence[A] = 0 first_occurrence[B] = 1 first_occurrence[C] = 5 first_occurrence[D] = 2

   Mảng Euler Tour có kích thước khoảng 2N - 1 (với N là số nút).

2. Kết nối LCA và RMQ: Nút có độ sâu nhỏ nhất trên đường đi giữa hai nút u và v trong cây chính là LCA(u, v). Khi chúng ta thực hiện Euler Tour, đường đi ngắn nhất trong cây giữa u và v sẽ tương ứng với một đoạn trong mảng Euler Tour, cụ thể là đoạn giữa lần xuất hiện đầu tiên của u và lần xuất hiện đầu tiên của v.

   Ví dụ: Tìm LCA(D, C). Lần xuất hiện đầu tiên của D là ở chỉ số 2. Lần xuất hiện đầu tiên của C là ở chỉ số 5. Xét đoạn trong mảng Euler Tour từ chỉ số 2 đến 5: Mảng nút: [D, B, A, C] Mảng độ sâu: [2, 1, 0, 1]

   Chúng ta cần tìm nút có độ sâu nhỏ nhất trong đoạn độ sâu [2, 5] của mảng euler_depths. Độ sâu nhỏ nhất ở đây là 0, tại chỉ số 4 trong mảng euler_depths (tương ứng với chỉ số 4 trong mảng euler_nodes). Nút tại chỉ số 4 trong euler_nodes là A. Vậy LCA(D, C) là A.

   Bài toán tìm nút có độ sâu nhỏ nhất trong một đoạn của mảng euler_depths chính là bài toán RMQ! Và chúng ta có thể sử dụng Sparse Table để giải quyết RMQ này trong O(1).

Để sử dụng Sparse Table cho RMQ trên mảng độ sâu này, Sparse Table cần lưu trữ chỉ số của phần tử nhỏ nhất trong một đoạn, thay vì giá trị nhỏ nhất đó.

• ST[i][j] sẽ lưu trữ chỉ số trong mảng euler_depths (hoặc euler_nodes) của nút có độ sâu nhỏ nhất trong đoạn [i, i + 2^j - 1] của mảng euler_depths.

• Khi xây dựng: ST[i][0] = i (chỉ số của phần tử tại vị trí i). ST[i][j]: So sánh euler_depths[ST[i][j-1]] và euler_depths[ST[i + (1 << (j-1))][j-1]]. ST[i][j] sẽ là chỉ số của phần tử có độ sâu nhỏ hơn trong hai chỉ số đó.

• Khi truy vấn LCA(u, v):

  1. Tìm idx_u = first_occurrence[u] và idx_v = first_occurrence[v].
  2. Nếu idx_u > idx_v, hoán đổi chúng.
  3. Truy vấn Sparse Table trên mảng euler_depths cho đoạn [idx_u, idx_v]. Sparse Table sẽ trả về chỉ số min_idx trong mảng Euler Tour nơi độ sâu là nhỏ nhất.
  4. Nút LCA(u, v) chính là euler_nodes[min_idx].

C++ Code Minh họa cho LCA sử dụng Sparse Table

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

const int MAXN_TREE = 100005; // Số nút tối đa trong cây
const int MAXN_EULER = MAXN_TREE * 2; // Kích thước tối đa mảng Euler Tour (~2N)
const int MAX_LOG_EULER = 18; // log2(MAXN_EULER)

std::vector<int> adj[MAXN_TREE]; // Danh sách kề của cây
int depth[MAXN_TREE]; // Độ sâu của các nút

int euler_nodes[MAXN_EULER]; // Mảng lưu ID nút trong Euler Tour
int euler_depths[MAXN_EULER]; // Mảng lưu độ sâu trong Euler Tour
int first_occurrence[MAXN_TREE]; // Lưu chỉ số lần xuất hiện đầu tiên của mỗi nút trong mảng Euler
int euler_size = 0; // Kích thước hiện tại của mảng Euler Tour

int lca_st[MAXN_EULER][MAX_LOG_EULER]; // Sparse Table cho LCA (lưu chỉ số trong mảng Euler)
int log_table_lca[MAXN_EULER]; // Bảng log_2 cho kích thước mảng Euler

// DFS để xây dựng Euler Tour, độ sâu, và first_occurrence
void dfs_euler(int u, int p, int d) {
    depth[u] = d;
    first_occurrence[u] = euler_size;

    euler_nodes[euler_size] = u;
    euler_depths[euler_size] = d;
    euler_size++;

    for (int v : adj[u]) {
        if (v != p) {
            dfs_euler(v, u, d + 1);
            // Ghi lại nút u khi quay lại từ nút con v
            euler_nodes[euler_size] = u;
            euler_depths[euler_size] = d;
            euler_size++;
        }
    }
}

// So sánh độ sâu tại hai chỉ số trong mảng euler_depths
// Trả về chỉ số của phần tử có độ sâu nhỏ hơn
int compare_depth_indices(int idx1, int idx2) {
    if (idx1 == -1) return idx2; // Trường hợp biên khi khởi tạo ST
    if (idx2 == -1) return idx1;
    return (euler_depths[idx1] < euler_depths[idx2]) ? idx1 : idx2;
}

// Xây dựng Sparse Table trên mảng euler_depths (lưu chỉ số)
void build_lca_st() {
    // Tiền xử lý bảng log_2 cho kích thước mảng Euler
    log_table_lca[1] = 0;
    for (int i = 2; i <= euler_size; i++) {
        log_table_lca[i] = log_table_lca[i / 2] + 1;
    }

    // Khởi tạo cột j=0: lưu chỉ số của chính nó trong mảng Euler
    for (int i = 0; i < euler_size; i++) {
        lca_st[i][0] = i;
    }

    // Xây dựng các cột j > 0
    for (int j = 1; j < MAX_LOG_EULER; j++) {
        for (int i = 0; i + (1 << j) <= euler_size; i++) {
            // So sánh độ sâu tại chỉ số lca_st[i][j-1] và lca_st[i + 2^(j-1)][j-1]
            // và lưu chỉ số có độ sâu nhỏ hơn vào lca_st[i][j]
            lca_st[i][j] = compare_depth_indices(
                lca_st[i][j - 1],
                lca_st[i + (1 << (j - 1))][j - 1]
            );
        }
    }
}

// Truy vấn Sparse Table trên mảng Euler để tìm chỉ số của nút có độ sâu nhỏ nhất trong đoạn [l, r]
// l, r là chỉ số trong mảng Euler (0-based index)
int query_lca_st(int l, int r) {
    int len = r - l + 1;
    int k = log_table_lca[len];
    // So sánh độ sâu tại chỉ số lca_st[l][k] và lca_st[r - 2^k + 1][k]
    return compare_depth_indices(
        lca_st[l][k],
        lca_st[r - (1 << k) + 1][k]
    );
}

// Hàm chính tìm LCA của hai nút u và v
// u, v là ID nút (0-based index)
int get_lca(int u, int v) {
    // Lấy chỉ số lần xuất hiện đầu tiên của u và v trong mảng Euler
    int idx_u = first_occurrence[u];
    int idx_v = first_occurrence[v];

    // Đảm bảo idx_u <= idx_v
    if (idx_u > idx_v) {
        std::swap(idx_u, idx_v);
    }

    // Truy vấn Sparse Table để tìm chỉ số min_idx trong mảng Euler
    // trong đoạn từ idx_u đến idx_v
    int min_depth_euler_idx = query_lca_st(idx_u, idx_v);

    // Nút tại chỉ số min_depth_euler_idx trong mảng euler_nodes chính là LCA
    return euler_nodes[min_depth_euler_idx];
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n; // Số nút trong cây (0 đến n-1)
    std::cout << "Nhap so nut trong cay: ";
    std::cin >> n;

    std::cout << "Nhap cac canh cua cay (dinh cha, dinh con - 0-based index):\n";
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // Cây vô hướng
    }

    // Xây dựng Euler Tour bắt đầu từ gốc (giả sử gốc là 0)
    dfs_euler(0, -1, 0);

    // Xây dựng Sparse Table trên mảng độ sâu Euler
    build_lca_st();

    int q; // Số lượng truy vấn LCA
    std::cout << "Nhap so luong truy van LCA: ";
    std::cin >> q;

    std::cout << "Nhap cac truy van LCA (u, v - 0-based index):\n";
    for (int i = 0; i < q; i++) {
        int u, v;
        std::cin >> u >> v;
        if (u < 0 || u >= n || v < 0 || v >= n) {
            std::cout << "ID nut khong hop le!\n";
        } else {
            std::cout << "LCA(" << u << ", " << v << ") la: " << get_lca(u, v) << "\n";
        }
    }

    return 0;
}

Giải thích Code LCA:

1. Constants and Global Arrays: Tăng kích thước tối đa cho các mảng để chứa cả dữ liệu cây gốc và dữ liệu từ Euler Tour (khoảng 2N). adj là danh sách kề cho cây. depth lưu độ sâu nút. euler_nodes, euler_depths lưu thông tin từ Euler Tour. first_occurrence lưu chỉ số lần xuất hiện đầu tiên. euler_size là biến đếm kích thước mảng Euler. lca_st là Sparse Table, và log_table_lca là bảng log cho kích thước Euler.
2. dfs_euler(int u, int p, int d):
   • Thực hiện DFS từ nút u, nút cha là p, độ sâu hiện tại là d.
   • Ghi lại độ sâu của u và chỉ số lần xuất hiện đầu tiên của u trong mảng Euler.
   • Thêm u và độ sâu d vào cuối mảng euler_nodes và euler_depths, tăng euler_size.
   • Duyệt qua các con v của u (trừ nút cha p). Gọi đệ quy dfs_euler(v, u, d+1).
   • Sau khi hoàn thành DFS cho cây con gốc v, chúng ta quay lại nút u. Ghi lại u và độ sâu d vào mảng Euler một lần nữa. Điều này hoàn thành "tour" qua nút v và quay về u.
3. compare_depth_indices(int idx1, int idx2): Hàm trợ giúp đơn giản để so sánh độ sâu tại hai chỉ số idx1 và idx2 trong mảng euler_depths. Trả về chỉ số có độ sâu nhỏ hơn. Được sử dụng trong quá trình xây dựng và truy vấn Sparse Table.
4. build_lca_st():
   • Tính log_table_lca cho kích thước euler_size hiện tại.
   • Khởi tạo cột j=0 của lca_st: lca_st[i][0] = i. Điều này có nghĩa là đoạn độ dài 1 ([i, i]) có phần tử nhỏ nhất (chính nó) tại chỉ số i trong mảng Euler.
   • Xây dựng các cột j > 0 tương tự như RMQ Sparse Table thông thường, nhưng sử dụng hàm compare_depth_indices để so sánh độ sâu và lưu chỉ số của phần tử nhỏ nhất.
5. query_lca_st(int l, int r):
   • Đây là hàm RMQ trên mảng euler_depths nhưng trả về chỉ số của phần tử nhỏ nhất.
   • Tính độ dài đoạn len = r - l + 1 và tìm k = log_table_lca[len].
   • Sử dụng compare_depth_indices để tìm chỉ số có độ sâu nhỏ nhất giữa hai đoạn con độ dài 2^k: [l, l + 2^k - 1] (đại diện bởi chỉ số lca_st[l][k]) và [r - 2^k + 1, r] (đại diện bởi chỉ số lca_st[r - (1 << k) + 1][k]).
6. get_lca(int u, int v):
   • Lấy chỉ số lần xuất hiện đầu tiên của u và v từ mảng first_occurrence.
   • Đảm bảo chỉ số bên trái nhỏ hơn hoặc bằng chỉ số bên phải.
   • Gọi query_lca_st trên đoạn [idx_u, idx_v] để tìm chỉ số min_depth_euler_idx trong mảng Euler nơi độ sâu nhỏ nhất xuất hiện.
   • Kết quả LCA chính là nút tại chỉ số min_depth_euler_idx trong mảng euler_nodes.
7. main: Đọc thông tin cây (số nút, các cạnh). Giả sử cây có gốc tại nút 0 và độ sâu 0. Gọi dfs_euler để tiền xử lý Euler Tour. Gọi build_lca_st để xây dựng Sparse Table trên dữ liệu Euler. Đọc số lượng truy vấn LCA và thực hiện các truy vấn bằng cách gọi get_lca, sau đó in kết quả.