3.4K 65 18

Đã đăng vào khoảng 13 giờ trước 32 phút đọc

Giải mã Sparse Table 2D Và Disjoint Sparse Table

MayFest2025 ContentCreator

Xin chào anh em, như đã hứa thì đây sẽ là phần tiếp theo của Sparse Table!

Anh em đã bao giờ "đứng hình" trước một bài toán xử lý lưới (grid) và cảm thấy não mình như muốn "đình công" chưa? Hay cần tìm tổng của một đoạn "ngày xửa ngày xưa" mà cái mảng dữ liệu nó cứ "trơ trơ như đá", không chịu thay đổi? Đừng lo, vì hôm nay tôi sẽ mang đến "song kiếm hợp bích" Sparse Table 2D và Disjoint Sparse Table để "giải cứu" anh em (và cả sự tỉnh táo của anh em nữa)!

Trong "cẩm nang" này, chúng ta sẽ cùng nhau "vén màn" bí ẩn của:

Sparse Table 2D: Chuyên gia "xử đẹp" truy vấn trên ma trận.
Disjoint Sparse Table: "Người hòa giải" cho các phép toán "khó tính", không chịu "lũy đẳng".

Tất cả sẽ được trình bày với "hương vị" C++ đậm đà và một chút "gia vị" hài hước. Anh em sẵn sàng chưa?

1. "Warm-up" Nhẹ Nhàng: Nhớ Lại "Bạn Cũ" Sparse Table 1D

Trước khi "bay" vào các chiều không gian cao hơn và những trò "chia chác" phức tạp, làm một "tách cà phê thuật toán" để ôn lại người bạn cũ Sparse Table 1D (ST1D) nào. Nếu anh em nào chưa "quen mặt", đừng lo, "em nó" khá là thân thiện đấy!

Đọc thêm về ST1D tại:

Phần 1: Sparse Table "Nhập Môn" - Giải Mã Siêu Năng Lực!
Phần 2: Sparse Table "Thực Chiến" - Hé Lộ Các "Tuyệt Kỹ"

1.1. "Sơ Yếu Lý Lịch" Của ST1D

ST1D là một cấu trúc dữ liệu được sinh ra để trả lời các truy vấn trên một phạm vi (range query) của một mảng tĩnh (static array) một cách "nhanh như điện". "Tĩnh" ở đây có nghĩa là sau khi anh em đã xây dựng bảng từ mảng ban đầu, mảng đó sẽ "yên vị", không thay đổi nữa. Nếu có "biến", anh em sẽ phải "xây lại từ đầu" – hơi cực một chút, nhưng "đáng đồng tiền bát gạo" cho tốc độ truy vấn!

Ý tưởng cốt lõi là tiền xử lý và lưu trữ kết quả cho các đoạn con có độ dài là lũy thừa của 2. Ví dụ, st[k][i] (hoặc st[i][k] tùy cách định nghĩa) sẽ lưu kết quả của một phép toán (như tìm min, max, GCD) trên đoạn con A[i...i + 2^k - 1].

1.2. Xây Dựng ST1D: Màn Khởi Động "N log N" Calo

Quá trình xây dựng bảng giống như xây một "kim tự tháp" kết quả, mỗi tầng được "chống" bởi tầng ngay dưới nó:

Tầng đáy (k=0): st[i][0] = A[i]. Đơn giản là giá trị của chính phần tử đó (đoạn dài $2^0=1$ ).
Các tầng tiếp theo (k>0): st[i][k] = operation(st[i][k-1], st[i + (1 << (k-1))][k-1]).
- operation ở đây là phép toán anh em muốn (ví dụ: min, max).
- (1 << (k-1)) là cách viết "cho ngầu" của $2^{k-1}$ trong C++.
- Công thức này "gộp" kết quả từ hai đoạn con dài $2^{k-1}$ liền kề (và có thể "gối" lên nhau) ở tầng dưới để tạo ra kết quả cho đoạn dài $2^k$ .

Quá trình tiền xử lý này "ngốn" $O(N \log N)$ thời gian, với N là "size" của mảng.

1.3. Truy Vấn ST1D: "Ảo Thuật" $O(1)$ Cho Phép Toán "Ngoan Ngoãn" (Lũy Đẳng)

Đây là lúc ST1D "tỏa sáng rực rỡ"! Với các phép toán lũy đẳng (idempotent) – tức là op(x,x) = x như min, max, GCD, AND, OR – chúng ta có thể trả lời truy vấn trong thời gian $O(1)$ "thần sầu".

Để truy vấn đoạn [L, R]:

Tính độ dài đoạn: len = R - L + 1.
Tìm k = log2(len) (trong C++, anh em có thể dùng log2 hoặc __lg – một hàm "bí mật" của GCC/Clang khá "bá đạo", hoặc tự xây bảng log tiền xử lý cho "chắc kèo").
Kết quả là operation(st[L][k], st[R - (1 << k) + 1][k]).

Hai đoạn con st[L][k] (từ L đến L+2^k-1) và st[R - (1 << k) + 1][k] (từ R-2^k+1 đến R) có thể "đè" lên nhau. Nhưng vì phép toán là lũy đẳng, việc một vài "em" phần tử được "tính sổ" hai lần không ảnh hưởng đến "đại cục". Giống như hỏi ai cao nhất trong hai nhóm người có vài "gương mặt thân quen" chung – người cao nhất "chung cuộc" vẫn không thay đổi!

1.4. Còn Mấy "Đứa Cứng Đầu" Không Lũy Đẳng (Như Tổng) Thì Sao?

Nếu phép toán "khó chiều", không lũy đẳng (ví dụ: phép cộng, sum(x,x) = 2x), anh em không thể để các đoạn "dẫm chân" lên nhau như trên được vì sẽ bị tính trùng – một lỗi "to như con voi". Thay vào đó, anh em phải "chia năm xẻ bảy" đoạn truy vấn thành các đoạn con rời rạc có độ dài là lũy thừa của 2. Việc này khiến truy vấn mất $O(\log N)$ thời gian.

1.5. "Show Hàng" Code C++ Cho Range Minimum Query (RMQ) 1D

Tưởng tượng anh em có một dãy các "nóc nhà thế giới" và muốn tìm "nóc" thấp nhất trong một khoảng nhìn nhất định.

// Dùng __lg cho tiện nếu dùng GCC/Clang, hoặc tự viết hàm log2
// int calcLog(int n) {
//     if (n == 0) return -1; // Hoặc xử lý lỗi theo cách khác
//     return 31 - __builtin_clz(n); // __builtin_clz đếm số bit 0 ở đầu
// }

const int MAXN = 100005;
const int MAX_LOGN = 20; // ceil(log2(MAXN))

int st[MAXN][MAX_LOGN];
int arr[MAXN]; // Mảng đầu vào
int precomputedLog1d[MAXN + 1];

void buildLogTable(int n)
{
    precomputedLog1d[1] = 0;
    for (int i = 2; i <= n; ++i)
        precomputedLog1d[i] = precomputedLog1d[i / 2] + 1;
}

void buildSt(int n)
{
    buildLogTable(n); // Tiền xử lý logarit

    for (int i = 0; i < n; ++i)
        st[i][0] = arr[i]; // Base case: đoạn dài 2^0 = 1

    for (int k = 1; k < MAX_LOGN; ++k)
    {
        for (int i = 0; (i + (1 << k)) <= n; ++i)
        {
            // st[k][i] theo định nghĩa trong nhiều tài liệu là st[i][k] ở đây
            st[i][k] = min(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
        }
    }
}

int queryMin(int L, int R)
{
    if (L > R || L < 0 || R >= MAXN)
        return 2e9; // Hoặc một giá trị vô cùng lớn khác, tùy bài toán
    int len = R - L + 1;
    if (len <= 0) // Xử lý đoạn không hợp lệ
        return 2e9;
    int k = precomputedLog1d[len]; // Sử dụng bảng log đã tiền xử lý
    // Hoặc int k = static_cast<int>(log2(len)); // Nếu không tiền xử lý log
    // Hoặc int k = calcLog(len);
    return min(st[L][k], st[R - (1 << k) + 1][k]);
}

int main()
{
    int n = 9;
    int exampleArr[] = {7, 2, 3, 0, 5, 10, 3, 12, 18};
    for (int i = 0; i < n; ++i)
        arr[i] = exampleArr[i];

    buildSt(n);

    cout << "Tim min trong doan [2,6] (0-indexed): " << queryMin(2, 6) << endl; // Output: 0
    cout << "Tim min trong doan [0,4] (0-indexed): " << queryMin(0, 4) << endl; // Output: 0
    cout << "Tim min trong doan [5,8] (0-indexed): " << queryMin(5, 8) << endl; // Output: 3
    return 0;
}

Lưu ý nhỏ: Cách định nghĩa st[k][i] hay st[i][k] có thể "nhảy múa" giữa các tài liệu. Trong ví dụ trên, st[i][k] lưu kết quả cho đoạn bắt đầu từ i và có độ dài $2^k$ . Quan trọng là anh em phải "nhất quán"!

Giờ thì, khi đã "làm nóng" xong với 1D, hãy cùng nhau "thám hiểm" những "gã khổng lồ" 2D!

2. "Đột Nhập Ma Trận": Sparse Table 2D Tung Hoành!

Thế giới không phải lúc nào cũng "phẳng lì" như một đường thẳng. Đôi khi, dữ liệu của chúng ta được "trải" trên một cái lưới – một bản đồ kho báu, một bảng pixel hình ảnh, hay đơn giản là một ma trận số "khó nhằn". Đây là lúc Sparse Table 2D (ST2D) "bước ra sân khấu", sẵn sàng "quét sạch" các truy vấn hình chữ nhật!

2.1. Thử Thách Mới: Lưới, Lưới Và Lưới!

ST2D "nâng cấp" ý tưởng của ST1D để "xử lý" các truy vấn trên một vùng hình chữ nhật (submatrix) của một ma trận 2D, thường là để tìm min/max trong "cái hộp" đó.

2.2. Hai "Trường Phái" Chính (Và Vì Sao Một "Phái" Hay Được "Lên Sóng" Hơn)

Có hai cách "tu luyện" ST2D chính:

"Trùm Cuối" Mảng 4D st[r][c][kx][ky] (hoặc hoán vị các chiều):
- Trong cách này, st[r][c][kx][ky] lưu trữ kết quả cho hình chữ nhật có kích thước $2^{kx} \times 2^{ky}$ bắt đầu từ ô (r,c). (Một số tài liệu có thể dùng st[kx][ky][r][c], thứ tự các chiều log có thể "bay nhảy", nhưng "tinh thần" là như nhau).
- Cứ tưởng tượng một cái bảng chứa các bảng con, mỗi bảng con lại là một ST1D cho một hàng (hoặc cột), và rồi lại có một ST "siêu to khổng lồ" khác chồng lên các kết quả đó! Đúng là "ST-ception"!
ST1D của các ST1D (Nghe thì "dễ thở", code thì "cũng được"):
- Xây dựng ST1D cho mỗi hàng của ma trận.
- Sau đó, xây dựng một ST1D khác "bên trên" các kết quả truy vấn của những ST1D hàng này. Tức là, để truy vấn một cột trên nhiều hàng, anh em sẽ truy vấn từng ST1D của hàng tương ứng, rồi "gom" kết quả của các truy vấn đó để "nạp" vào một ST1D "cấp cao" hơn.
- Cách này giống như có một "chuyên gia ST" cho mỗi hàng, và một "quản lý ST tổng" điều phối các chuyên gia này.

Trong bài viết này, chúng ta sẽ "focus" vào phương pháp mảng 4D vì nó "quen mặt" hơn trong các ví dụ "try hard" thi đấu, nhưng anh em nên "bỏ túi" là có cả "chiêu" kia nữa nhé.

2.3. Tiền Xử Lý "Quái Vật" 4D ( $O(N \cdot M \cdot \log N \cdot \log M)$ )

Việc xây dựng ST2D 4D hơi "cồng kềnh" hơn một chút, nhưng vẫn dựa trên nguyên tắc "chia để trị" và "quy hoạch động thần chưởng":

Trường hợp "em út": st[r][c][0][0] = matrix[r][c]. Đây là kết quả cho các hình chữ nhật $2^0 \times 2^0$ (tức là 1x1 "bé xinh").
Xây dựng "leo thang": Có nhiều cách tổ chức vòng lặp, nhưng một cách "thông dụng" là:
1. Bước 1: "Cày" theo chiều rộng cho từng hàng (tạo các ST1D theo hàng). Với mỗi hàng r, và với mỗi ky từ 1 đến $\log M$ : Với mỗi cột c sao cho đoạn [c, c + 2^ky - 1] không "lố" M: st[r][c][0][ky] = operation(st[r][c][0][ky-1], st[r][c + (1<<(ky-1))][0][ky-1]) (Lưu ý: st[r][c][0][ky] ở đây là kết quả cho đoạn matrix[r][c...c+2^ky-1]. Chỉ số kx=0 ngụ ý là chỉ xét trong 1 hàng).
2. Bước 2: "Leo" theo chiều cao dựa trên kết quả ở Bước 1 (kết hợp các ST1D hàng). Với mỗi kx từ 1 đến $\log N$ : Với mỗi ky từ 0 đến $\log M$ : (lưu ý, ky=0 tương ứng với các cột đơn lẻ đã được xử lý ở Bước 1 nếu ta coi st[r][c][0][0] là kết quả của ST1D trên cột đó, hoặc có thể hiểu là các đoạn 1x$2^{ky}$ đã tính ở bước 1) Với mỗi hàng r sao cho đoạn [r, r + 2^kx - 1] không "lố" N: Với mỗi cột c sao cho đoạn [c, c + 2^ky - 1] không "lố" M: st[r][c][kx][ky] = operation(st[r][c][kx-1][ky], st[r + (1<<(kx-1))][c][kx-1][ky]) Công thức này "gộp" kết quả từ hai hình chữ nhật $2^{kx-1} \times 2^{ky}$ nằm "chồng" lên nhau theo chiều dọc.
Một cách khác để hình dung bước 2 (và thường thấy trong các "bí kíp" code) là trực tiếp "gộp" 4 hình chữ nhật con $2^{kx-1} \times 2^{ky-1}$ : st[r][c][kx][ky] = op(op(st[r][c][kx-1][ky-1], st[r + (1<<(kx-1))][c][kx-1][ky-1]), op(st[r][c + (1<<(ky-1))][kx-1][ky-1], st[r + (1<<(kx-1))][c + (1<<(ky-1))][kx-1][ky-1]))

Thứ tự các vòng lặp kx và ky rất quan trọng để đảm bảo các " đàn em" đã được tính toán. Thường thì người ta sẽ lặp kx ở vòng ngoài, rồi ky, rồi r, rồi c.

"Nó giống như lắp ráp một lâu đài LEGO khổng lồ. Đầu tiên, anh em xây các bức tường thành (ST1D dọc theo một chiều), sau đó anh em 'chồng' các bức tường đó lên nhau để xây các cấu trúc 'cao chọc trời' hơn (ST1D dọc theo chiều còn lại)."

Độ phức tạp tiền xử lý là $O(N \cdot M \cdot \log N \cdot \log M)$ và "dung lượng" lưu trữ cũng "khủng" tương tự.

2.4. Truy Vấn Trong "Không Gian 2 Chiều" ( $O(1)$ Cho Phép Toán "Ngoan Hiền")

Để truy vấn hình chữ nhật từ (r1, c1) đến (r2, c2) (tọa độ 0-indexed):

Tính chiều dài và chiều rộng: lenR = r2 - r1 + 1 lenC = c2 - c1 + 1
Tính các "số mũ" logarit: kx = precomputedLog[len_r] (hoặc static_cast<int>(log2(len_r))) ky = precomputedLog[len_c] (hoặc static_cast<int>(log2(len_c)))
Kết quả là operation của 4 hình chữ nhật con "màu nhiệm" đã được tiền xử lý (cần phép toán lũy đẳng): val1 = st[r1][c1][kx][ky] val2 = st[r2 - (1 << kx) + 1][c1][kx][ky] val3 = st[r1][c2 - (1 << ky) + 1][kx][ky] val4 = st[r2 - (1 << kx) + 1][c2 - (1 << ky) + 1][kx][ky] answer = operation(operation(val1, val2), operation(val3, val4))

"Cũng giống như 1D, chúng ta 'chộp' lấy bốn 'siêu ô gạch' (có thể 'đè' lên nhau) đã được 'mài giũa' sẵn để 'phủ kín' hoàn hảo hình chữ nhật truy vấn. Phép Max/Min 'chẳng thèm' bận tâm đến sự 'dẫm chân' đó!"

2.5. "Show Hàng" Code C++: 2D Range Maximum Query (Tìm Ô "Nóng Bỏng" Nhất Trên Bản Đồ Nhiệt)

Tưởng tượng anh em có một bản đồ nhiệt của một khu "quẩy", và anh em muốn tìm ô có nhiệt độ "cháy" nhất trong một vùng hình chữ nhật bất kỳ.

const int MAX_DIM = 505; // Kích thước tối đa cho mỗi chiều
const int LOG_DIM = 10;  // ceil(log2(MAX_DIM))

int matrix[MAX_DIM][MAX_DIM];
// st[r][c][kx][ky] lưu max của hình chữ nhật bắt đầu tại (r,c) kích thước 2^kx * 2^ky
int st[MAX_DIM][MAX_DIM][LOG_DIM][LOG_DIM];
int precomputedLog2d[MAX_DIM + 1];

void buildLogTable(int maxVal)
{
    precomputedLog2d[1] = 0;
    for (int i = 2; i <= maxVal; ++i)
        precomputedLog2d[i] = precomputedLog2d[i / 2] + 1;
}

// Hàm gộp, ở đây là tìm max
int mergeOp(int a, int b)
{
    return max(a, b);
}

int mergeOp(int a, int b, int c, int d)
{
    return max({a, b, c, d});
}

void buildSt(int R, int C)
{ // R hàng, C cột
    buildLogTable(max(R, C));

    // Khởi tạo st[r][c][0][0]
    for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c)
            st[r][c][0][0] = matrix[r][c];

    // Xây dựng theo chiều rộng (ky) cho mỗi hàng, với kx = 0 (mở rộng theo cột)
    for (int r = 0; r < R; ++r)
    {
        for (int ky = 1; ky < LOG_DIM; ++ky)
        {
            for (int c = 0; (c + (1 << ky)) <= C; ++c)
            {
                st[r][c][0][ky] = mergeOp(st[r][c][0][ky - 1],
                                                 st[r][c + (1 << (ky - 1))][0][ky - 1]);
            }
        }
    }

    // Xây dựng theo chiều cao (kx) cho mỗi cấu hình chiều rộng (ky) đã có
    // (mở rộng theo hàng, dựa trên các đoạn 2^ky đã tính)
    for (int kx = 1; kx < LOG_DIM; ++kx)
    {
        for (int r = 0; (r + (1 << kx)) <= R; ++r)
        {
            for (int ky = 0; ky < LOG_DIM; ++ky)
            { // Duyệt qua tất cả các ky đã tính
                for (int c = 0; (c + (1 << ky)) <= C; ++c)
                { // Kiểm tra biên cho ky
                    // Nếu (1 << ky) > C và ky > 0 thì không cần tính nữa, trừ khi ky=0 (đã tính ở trên)
                    // Điều kiện này đảm bảo (1 << ky) là độ dài hợp lệ hoặc ky=0 (độ dài 1)
                    if (ky > 0 && (1 << ky) > C)
                        continue;
                    if (ky == 0 && (c + 1) > C)
                        continue;

                    st[r][c][kx][ky] = mergeOp(st[r][c][kx - 1][ky],
                                                      st[r + (1 << (kx - 1))][c][kx - 1][ky]);
                }
            }
        }
    }
}

// Truy vấn hình chữ nhật từ (r1, c1) đến (r2, c2) (0-indexed, bao gồm cả hai đầu)
int queryMax(int r1, int c1, int r2, int c2)
{
    if (r1 > r2 || c1 > c2 || r1 < 0 || c1 < 0 || r2 >= MAX_DIM || c2 >= MAX_DIM)
        return -2e9; // Hoặc giá trị min phù hợp

    int len_r = r2 - r1 + 1;
    int len_c = c2 - c1 + 1;
    if (len_r <= 0 || len_c <= 0)
        return -2e9;

    int kx = precomputedLog2d[len_r];
    int ky = precomputedLog2d[len_c];

    int val1 = st[r1][c1][kx][ky];
    int val2 = st[r2 - (1 << kx) + 1][c1][kx][ky];
    int val3 = st[r1][c2 - (1 << ky) + 1][kx][ky];
    int val4 = st[r2 - (1 << kx) + 1][c2 - (1 << ky) + 1][kx][ky];

    return mergeOp(val1, val2, val3, val4);
}

int main()
{
    int R = 4, C = 4;
    int exampleMatrix[MAX_DIM][MAX_DIM] = {
        {5, 8, 2, 4},
        {7, 12, 9, 1},
        {1, 4, 7, 13},
        {3, 5, 6, 8}};
    for (int i = 0; i < R; ++i)
    {
        for (int j = 0; j < C; ++j)
        {
            matrix[i][j] = exampleMatrix[i][j];
        }
    }

    buildSt(R, C);

    // Tìm nhiệt độ cao nhất trong vùng từ (1,1) đến (2,2)
    cout << "Max trong vung [(1,1) - (2,2)]: " << queryMax(1, 1, 2, 2) << endl; // Ouput: 12
    // Tìm nhiệt độ cao nhất trong toàn bản đồ
    cout << "Max trong toan ban do [(0,0) - (3,3)]: " << queryMax(0, 0, 3, 3) << endl; // Ouput: 13
    cout << "Max trong vung [(0,2) - (1,3)]: " << queryMax(0, 2, 1, 3) << endl;        // Ouput: 9

    return 0;
}

2.6. "Đất Diễn" và Các Bài Toán "Hóc Búa"

Tìm max/min trong một "ô đất" của lưới: Ứng dụng "ruột" và phổ biến nhất.
Codeforces 713D - Animals and Puzzle : Tìm "tấm ảnh vuông" lớn nhất toàn số 1 nằm gọn trong một hình chữ nhật truy vấn.
- Cách "phá đảo": Đầu tiên, "cày" dp[i][j] là kích thước của hình vuông "xịn" nhất toàn số 1 có góc dưới phải tại (i,j).
- Sau đó, "dựng" ST2D trên "bản đồ" dp này. Để trả lời truy vấn cho hình chữ nhật (r1,c1)-(r2,c2), ta "chặt nhị phân" (binary search) trên kích thước k của hình vuông.
- Với một k cho trước, ta cần "soi" xem có "em" hình vuông nào kích thước k không. Điều này tương đương với việc tìm max trong mảng dp trên một vùng con (r1+k-1, c1+k-1) đến (r2,c2).
- Nếu max dp trong vùng này $\ge k$ , thì "bingo", có hình vuông kích thước k.
- "Bài này giống như anh em muốn tìm tấm ảnh con mèo (toàn số 1) 'bự' nhất có thể 'cắt' ra từ một trang báo (hình chữ nhật truy vấn), biết rằng anh em đã 'đo' sẵn kích thước ảnh mèo lớn nhất kết thúc ở mọi 'tọa độ' có thể trên trang báo."
Xử lý ảnh: Tìm vùng "sáng chói" nhất/"tối om" nhất, "soi" đối tượng dựa trên đặc trưng trong một "khung cửa sổ".
Phát triển game: Tìm "chiến binh" mạnh nhất trong một "khu vực giao tranh" trên bản đồ.

Mặc dù truy vấn $O(1)$ "nghe rất kêu", nhưng chi phí tiền xử lý và "độ ngốn" không gian $O(N \cdot M \cdot \log N \cdot \log M)$ có thể khá "chát". Đối với các lưới "nhỏ xinh" hoặc khi $\log N \cdot \log M$ không quá "khủng", ST2D là một "ứng cử viên sáng giá". Nếu không, các "cao thủ" khác như Segment Tree 2D (nếu cần "update" hoặc phép toán "khó chiều") hoặc K-D Tree có thể được "triệu hồi", dù chúng có những "điểm yếu" khác.

3. Disjoint Sparse Table: Khi "Chia Sẻ" (Chồng Lấn) KHÔNG Còn Là "Mối Bận Tâm"!

Người bạn ST1D của chúng ta rất "kết" min/max/GCD vì tính lũy đẳng (op(x,x) = x). Nhưng nếu anh em cần tính Tổng Dải (Range Sum) thì sao? sum(x,x) = 2x – úi chà, các đoạn "dẫm chân" lên nhau sẽ làm anh em "tính nhầm" các phần tử chung hai lần! Đó là một lỗi "không thể chấp nhận được".

Đây là lúc Disjoint Sparse Table (DST) "xuất hiện như một vị thần"! Nó cho phép truy vấn $O(1)$ cho bất kỳ phép toán kết hợp (associative) nào, ngay cả khi nó "chảnh", không lũy đẳng, sau khi tiền xử lý $O(N \log N)$ .

3.1. "Bí Kíp" Cốt Lõi: Các Khối "Không Đụng Hàng" (Rời Rạc)

Thay vì "nhắm mắt làm ngơ" cho các đoạn truy vấn "ôm nhau", DST đảm bảo rằng các đoạn con được "góp gạo thổi cơm chung" để tạo thành kết quả cuối cùng là hoàn toàn "không dây dưa" gì đến nhau. Nó làm điều này bằng cách tiền xử lý các giá trị tổng tiền tố (prefix sum/product/etc.) và tổng hậu tố (suffix sum/product/etc.) bên trong các khối (block) có kích thước là lũy thừa của 2.

3.2. Xây Dựng DST: Logic Tiền Tố/Hậu Tố "Thông Minh" Trong Khối và "Reset" Đúng Lúc

Việc xây dựng DST thường bao gồm:

Phân cấp (Levels): Tương tự ST thông thường, DST có các "tầng lớp" h tương ứng với kích thước khối $2^h$ .
"Xử Lý" Từng Khối (Block Processing):
- Với mỗi cấp h và mỗi khối bắt đầu tại chỉ số c (thường là bội số của $2^h$ $2^{h}$ hoặc một vị trí "trung tâm" của khối lớn hơn), ta tính toán:
  - Giá trị tiền tố prefixVal[h][i]: Kết quả của phép toán trên các phần tử từ đầu khối (hoặc một điểm "tham chiếu" trong khối) đến i.
  - Giá trị hậu tố suffixVal[h][i]: Kết quả của phép toán trên các phần tử từ i đến cuối khối (hoặc một điểm "tham chiếu").
Logic "Reset Khéo Léo": Điều quan trọng là các tính toán tiền tố/hậu tố này được "làm mới" cho mỗi khối. Ví dụ, trong một số cách cài đặt, điều này được thực hiện bằng cách sử dụng mask = (1 << h) - 1 và kiểm tra if((i & mask) == mask) (cho tiền tố, reset khi i chạm đến cuối một "tiểu khối" bên trong khối lớn hơn) hoặc if((i & mask) == 0) (cho hậu tố, reset khi i là đầu một "tiểu khối"). Một biến curVal được reset về "phần tử trung hòa" của phép toán.
Phần tử trung hòa (Neutral Element): Đây là "siêu anh hùng thầm lặng". Nó là giá trị mà khi "kết hợp" với bất kỳ phần tử x nào cũng không làm "xi nhê" x. Ví dụ: 0 cho phép cộng/XOR, 1 cho phép nhân, INT_MAX cho min, INT_MIN cho max. "Nạp" sai phần tử trung hòa là "toang" cả bảng!

3.3. Truy Vấn DST ( $O(1)$ Với Phép Toán "Biết Điều" - Kết Hợp)

Để truy vấn đoạn [L, R]:

Trường hợp "bé hạt tiêu": Nếu L == R, trả về arr[L].
Tìm "tầng lớp" h phù hợp: Mức h được chọn sao cho khối có kích thước $2^h$ là khối lớn nhất mà không "vượt mặt" điểm chung của L và R khi nhìn từ hai đầu. Một cách "kinh điển" là h = __lg(L ^ R) (log cơ số 2 của XOR của L và R) hoặc (sizeof(int)*8 - 1) - __builtin_clz(L ^ R) (đếm số bit 0 ở đầu của XOR, với sizeof(int)*8 là số bit của int). Phép XOR ở đây giúp tìm ra bit cao nhất mà L và R "khác biệt", từ đó xác định được "ranh giới" khối chung lớn nhất mà L và R thuộc về hai "nhánh con" khác nhau.
"Góp Gạo" Kết Quả: Câu trả lời là combine(suffixVal[h][L], prefixVal[h][R]). suffixVal[h][L] là kết quả hậu tố từ L trong khối kích thước $2^h$ của nó, và prefixVal[h][R] là kết quả tiền tố đến R trong khối kích thước $2^h$ của nó. Vì cách xây dựng "thần sầu", hai phần này sẽ "gặp nhau" và "ôm trọn" toàn bộ đoạn [L,R] mà không "dẫm chân" lên nhau.

3.4. "Show Hàng" Code C++: Range Product Modulo (Nhân Cả Dãy Rồi "Xin Tí" Dư)

Tưởng tượng anh em có một dãy các "viên đá vô cực", mỗi viên có một "sức mạnh" nhất định. Khi "hợp nhất", sức mạnh của chúng nhân với nhau, nhưng vì "quá bá đạo", kết quả phải được lấy modulo một số P "khiêm tốn".


// Hàm tính log2 thủ công nếu không có __lg hoặc log2 (int)
// int floor_log2(int n) {
//     if (n == 0) return -1;
//     int log_val = 0;
//     while ((1 << (log_val + 1)) <= n) {
//         log_val++;
//     }
//     return log_val;
// }

// Hoặc dùng __builtin_clz cho GCC/Clang
int calcLog2(int n)
{
    if (n == 0)
        return -1; // Hoặc xử lý lỗi
    // Giả sử int là 32 bit, nếu không cần sizeof(int) * 8
    return (31) - __builtin_clz(static_cast<unsigned int>(n));
}

template <typename T, T (*opFunc)(T, T), T (*neutralElementFunc)()>
struct DisjointSparseTable
{
    int N;
    vector<vector<T>> prefTable; // prefTable[h][i]
    vector<vector<T>> suffTable; // suffTable[h][i]
    vector<T> originalArr;       // Lưu mảng gốc để xử lý trường hợp L==R

    DisjointSparseTable(const vector<T> &arr)
    {
        N = arr.size();
        if (N == 0)
            return;
        originalArr = arr;

        int maxLogVal = (N > 0) ? calcLog2(N) + 1 : 1; // Số tầng
        prefTable.assign(maxLogVal, vector<T>(N));
        suffTable.assign(maxLogVal, vector<T>(N));

        // Tầng 0: mỗi phần tử là một khối, prefix và suffix là chính nó
        for (int i = 0; i < N; ++i)
        {
            prefTable[0][i] = arr[i];
            suffTable[0][i] = arr[i];
        }

        for (int h = 1; h < maxLogVal; ++h)
        {
            int lenHalf = (1 << (h - 1)); // Kích thước của mỗi nửa khối nhỏ
            int lenFull = (1 << h);       // Kích thước của khối hiện tại đang xét tiền tố/hậu tố

            for (int idx = 0; idx * lenFull < N; ++idx)
            {
                int curStart = idx * lenFull;
                int curEnd = min(N, curStart + lenFull);

                // Tính suffix cho nửa trái của khối (hoặc toàn khối nếu nó là khối rìa)
                // và prefix cho nửa phải của khối
                int mid = curStart + lenHalf;

                // Suffix cho nửa trái
                if (mid - 1 < N && mid - 1 >= curStart)
                {
                    suffTable[h][mid - 1] = arr[mid - 1];
                    for (int i = mid - 2; i >= curStart && i < N; --i)
                        suffTable[h][i] = opFunc(arr[i], suffTable[h][i + 1]);
                }

                // Prefix cho nửa phải
                if (mid < N && mid < curEnd)
                {
                    prefTable[h][mid] = arr[mid];
                    for (int i = mid + 1; i < curEnd && i < N; ++i)
                        prefTable[h][i] = opFunc(prefTable[h][i - 1], arr[i]);
                }
            }
        }
    }

    T query(int l, int r)
    {
        if (l > r || l < 0 || r >= N)
            return neutralElementFunc();
        if (l == r)
            return originalArr[l]; // Trả về giá trị gốc

        // Tìm mức h sao cho L và R nằm ở 2 block con khác nhau của 1 block lớn hơn
        // Hoặc L và R nằm ở biên của 2 block liền kề ở mức h
        int hQuery = (l == r) ? 0 : calcLog2(l ^ r);
        // ^ Logic này phổ biến, tìm bit khác biệt cao nhất
        // hQuery thực ra là tầng log mà L và R nằm ở 2 nhánh khác nhau của một khối 2^(hQuery+1)

        // Kết quả là suffix của L và prefix của R ở cùng mức hQuery.
        // Các giá trị này được xây dựng để "gặp nhau" và bao phủ đoạn [L,R].
        return opFunc(suffTable[hQuery][l], prefTable[hQuery][r]);
    }
};

// Ví dụ cho Range Product Modulo
long long getMulMod(long long a, long long b)
{
    return (a * b) % 1000000007LL;
}

long long get1LLFunc()
{
    return 1LL;
}

int main()
{ // Bỏ comment để chạy thử DST
    vector<long long> A_dst = {2, 3, 4, 5, 6};
    DisjointSparseTable<long long, getMulMod, get1LLFunc> dst_example(A_dst);

    // Truy vấn tích đoạn A[2..2]
    cout << "Product of A[2..2] = " << dst_example.query(2, 2) << endl; // Ouput: 4

    vector<long long> B_dst = {10, 20};
    DisjointSparseTable<long long, getMulMod, get1LLFunc> DSTExample(B_dst);
    cout << "Product of B[0..1] = " << DSTExample.query(0, 1) << endl; // Ouput: 200
    cout << "Product of B[0..0] = " << DSTExample.query(0, 0) << endl; // Ouput: 10

    return 0;
}

Lưu ý về code DST: Cài đặt DST có "muôn hình vạn trạng". Đoạn code trên cố gắng "bắt chước" ý tưởng chung từ các "cao nhân" (đặc biệt là cách xây dựng prefix/suffix trong các block con). Logic l ^ r rất "vi diệu" để xác định đúng "điểm chia" hoặc "tầng lớp" chi tiết cần thiết.

3.5. Ứng Dụng "Không Đụng Hàng"

CodeChef SEGPROD - Product on the segment by modulo: Đây là bài toán "sinh ra để dành cho" DST. Phép nhân modulo một số (đặc biệt là "hợp số khó ưa") không lũy đẳng, nên ST thường "bó tay" cho truy vấn $O(1)$ . DST "xử đẹp" vấn đề này.
Các bài toán "MARS" (Calculate MARS, Maximize MARS): Được "điểm mặt gọi tên" là các bài "khó nhai" trên các diễn đàn có thể "thịt" bằng DST, cho thấy "tiềm năng vô hạn" của nó trong các vấn đề "hack não" hơn.

DST thực sự là một "vũ khí hạng nặng" khi anh em cần tốc độ $O(1)$ cho các phép toán kết hợp trên mảng tĩnh mà "em nó" lại "chảnh", không chịu lũy đẳng. Tuy nhiên, sự phức tạp trong "lắp ráp" và "sửa lỗi" có thể "gây khó dễ" hơn so với ST "truyền thống".

4. Mẹo "Bỏ Túi" & Những Khoảnh Khắc "Ối Dời Ơi!" (Cạm Bẫy Ngọt Ngào)

Dù anh em đang "chiến đấu" với ST1D, ST2D hay DST, luôn có những "cạm bẫy" chực chờ "xơi tái". Dưới đây là một số mẹo và những lỗi "kinh điển" mà các "đồng code" hay "sa chân lỡ bước":

4.1. "Trí Khôn" Sparse Table Nói Chung

0-based vs 1-based Indexing: "Kẻ thù truyền kiếp" của nhiều coder. Hãy "nhất quán"! Nếu mảng của anh em là 0-indexed, hãy "chắc kèo" tất cả các vòng lặp và truy vấn đều "chung một nhịp đập". "Nhảy qua nhảy lại" giữa hai hệ thống này là "công thức cho thảm họa" (hay ít nhất là vài giờ debug "mệt nghỉ").
"Ma Trận" Tính Toán Logarit:
- log2(len): Trả về double, cần "ép" sang int. "Cẩn thận" với len = 0 hoặc len = 1.
- __lg(len) (GCC/Clang extension): Trả về int, "tiện lợi đủ đường", nhưng không phải "lúc nào cũng có mặt". __lg(0) là "không xác định".
- Mảng log tiền xử lý precomputedLog[i] = floor(log2(i)): "Nhanh như chớp" khi truy cập, nhưng "ngốn" bộ nhớ $O(N)$ và có thể bị "cache miss" (dù thường là không đáng kể cho $N$ vừa phải). precomputedLog[1] = 0 là một "khởi đầu tốt đẹp".
- __builtin_clz(x) (count leading zeros): log2(x) = (sizeof(int)*8 - 1) - __builtin_clz(x). "Nhanh hơn", nhưng "đề phòng" với x=0.
- Cạm bẫy logarit: "Luôn 'soi' kỹ các phép tính logarit của anh em. Chúng có thể 'lén lút' như một con mèo!"
"Canh Chừng" Giới Hạn Vòng Lặp:
- Khi "dựng" bảng: for (int k = 1; (1 << k) <= N; ++k) và for (int i = 0; (i + (1 << k)) <= N; ++i).
- Chú ý (i + (1 << k)) <= N để đảm bảo đoạn [i, i + 2^k - 1] "nằm gọn" trong mảng. Một lỗi "off-by-one" ở đây có thể dẫn đến "tai nạn" truy cập ngoài mảng.
- "Lỗi off-by-one: những ninja của thế giới bug, 'im lặng nhưng chết người'."
"Lời Thề" Dữ Liệu Tĩnh: Nhắc lại lần nữa, ST chỉ "chơi" với mảng "bất biến". Nếu dữ liệu "thay lòng đổi dạ", anh em phải "xây lại cơ đồ" hoặc "cầu cứu" cấu trúc khác (như Segment Tree).

4.2. "Đèn Đỏ" Cảnh Báo Khi Dùng ST2D

"Ma Hồn Trận" Thứ Tự Index Mảng 4D: st[kx][ky][r][c] hay st[r][c][kx][ky]? Cách anh em "sắp đặt" thứ tự các chiều (log_height, log_width, start_row, start_col) là "sống còn". "Nhầm lẫn" ở đây sẽ dẫn đến việc "móc" sai giá trị hoặc "ăn" lỗi runtime.
"Bài Toán" Tối ưu Cache: Thứ tự st[kx][ky][r][c] có thể không "chiều lòng" cache bằng st[r][c][kx][ky] nếu anh em thường xuyên "hỏi thăm" các vùng "gần gũi" nhau về mặt không gian (r,c). Tuy nhiên, khi "xây dựng", việc lặp qua kx, ky ở vòng ngoài có thể "ổn áp" hơn. Cách tiếp cận "ST1D của các ST1D" có thể "ghi điểm" về cache ở đây vì nó "xử lý" các hàng/cột một cách "tuần tự" hơn.
- "Mảng 4D: nó giống như cố gắng tìm đôi tất của anh em trong một khối tesseract vậy. Cẩn thận với các chiều không gian!"
"Luật Bất Thành Văn" Thứ Tự Xây Dựng (Build Order): Khi "dựng" st[r][c][kx][ky], anh em phải "đảm bảo" rằng các "đàn em" cho kx-1 và ky-1 đã "ra đời". Ví dụ, tính tất cả các st[...][0][ky] (mở rộng theo chiều rộng cho từng hàng), sau đó dùng chúng để tính st[...][kx][ky] (mở rộng theo chiều cao).
Bộ Nhớ "Siêu To Khổng Lồ": $O(N \cdot M \cdot \log N \cdot \log M)$ có thể "khủng khiếp" lắm đấy. Hãy "chắc kèo" là bài toán của anh em "chịu nổi nhiệt".

4.3. "Bãi Mìn" Với Disjoint ST

"Đau Đầu" Logic Ranh Giới Khối (Block Boundary): Việc xác định "chuẩn không cần chỉnh" điểm bắt đầu và kết thúc của các khối ở mỗi cấp là "cực kỳ quan trọng". "Sai một ly, đi một dặm" (và "ôm" WA).
"Nhiệm Vụ Bất Khả Thi?" Logic Reset Tiền Tố/Hậu Tố: Khi "nhảy" sang một khối mới ở cùng một cấp, các giá trị "tích cóp" tiền tố/hậu tố phải được "tẩy trần" bằng phần tử trung hòa. Điều kiện if((i & mask) == mask) hoặc if((i & mask) == 0) trong một số "bí kíp" code chính là để "thi hành nhiệm vụ" này. "Bỏ quên" reset là một lỗi "thường như cơm bữa".
"Chọn Mặt Gửi Vàng" Phần Tử Trung Hòa (Neutral Element):
- Phải chọn "đúng người đúng tội" cho phép toán của anh em! 0 cho tổng/XOR, 1 cho tích, $\infty$ cho min, $-\infty$ cho max.
- "Chọn sai phần tử trung hòa cũng giống như mang một quả bóng chuyền đến một trận đấu bowling vậy. Hoàn toàn 'phế'!"
"Cân Não" Thao Tác Bit Trong Truy Vấn: __lg(L ^ R) hay (sizeof(int)*8 - 1) - __builtin_clz(L ^ R) là những "chiêu thức" phổ biến để tìm mức h "ưng ý". "Hiểu sai hoặc dùng sai" các hàm này có thể dẫn đến việc "chọn nhầm" khối. __builtin_clz(0) là "không xác định", cần "chăm sóc đặc biệt".

"Nắm vững" những điều này sẽ giúp anh em "né" được nhiều giờ debug "đau khổ triền miên" và "tự tin khoe cá tính" hơn khi triển khai các "biến thể" Sparse Table này.

5. "Hạ Màn": Khi Nào Nên "Triệu Hồi" Các "Cao Thủ Ma Trận" Này?

Vậy là chúng ta đã cùng nhau "phiêu lưu" qua thế giới "kỳ diệu" (và đôi khi hơi "hack não") của Sparse Table 2D và Disjoint Sparse Table. "Túm cái váy lại" thì:

Sparse Table 1D "cơ bản": "Tuyệt vời ông mặt trời" cho truy vấn $O(1)$ trên mảng tĩnh với các phép toán "ngoan hiền" (lũy đẳng như min, max, GCD). Với các phép toán "biết điều" (kết hợp) khác (như tổng), "em nó" vẫn cho truy vấn $O(\log N)$ "ổn áp".
Sparse Table 2D: "Nâng cấp sức mạnh" lên lưới 2D, cho phép truy vấn $O(1)$ trên các "ô đất" hình chữ nhật (với phép toán lũy đẳng). "Cực kỳ hữu dụng" cho các bài toán xử lý lưới, tìm kiếm hình vuông/chữ nhật "bá đạo nhất" có tính chất "đặc biệt". Nhưng hãy "dè chừng" chi phí tiền xử lý và bộ nhớ $O(N \cdot M \cdot \log N \cdot \log M)$ "không phải dạng vừa đâu".
Disjoint Sparse Table: "Vũ khí bí mật" khi anh em "thèm khát" truy vấn $O(1)$ cho các phép toán kết hợp nhưng "chảnh chọe" không nhất thiết lũy đẳng (như tổng, tích modulo) trên mảng tĩnh. Logic "dựng nhà" phức tạp hơn một chút với các khối tiền tố/hậu tố "không đụng hàng".

Khi nào "xài" cái nào?

Mảng 1D, phép toán lũy đẳng, cần truy vấn "nhanh như điện giật"? ST1D thẳng tiến!
Mảng 1D, phép toán kết hợp (không lũy đẳng), "chấp nhận" truy vấn $O(\log N)$ ? ST1D vẫn "ngon"!
Lưới 2D, phép toán lũy đẳng, truy vấn hình chữ nhật $O(1)$ ? ST2D là "ngôi sao sáng" (nếu bộ nhớ "rủng rỉnh").
Mảng 1D, phép toán kết hợp (không lũy đẳng), và anh em "thực sự, thực sự" cần truy vấn $O(1)$ (ví dụ, số lượng truy vấn "khủng bố")? Disjoint Sparse Table có thể là "cứu tinh", dù "lắp ráp" có hơi "xoắn não".

Hy vọng rằng với "cẩm nang" này, anh em không chỉ "thông tường" hơn về các loại Sparse Table "cao cấp" này mà còn có thể "tự tin tung chiêu" áp dụng chúng vào các bài toán của mình – và có lẽ, anh em sẽ "mỉm cười tủm tỉm" một chút khi nhớ lại những ví dụ "khó đỡ" trong bài viết này.

Chúc anh em code vui và "né" bug thành công! Nhớ nhé, "With great power comes great $O(1)$ query time!" (Tạm dịch: Sức mạnh càng "khủng", thời gian truy vấn $O(1)$ càng "phê"!).

Sparse Table Data Structure DSA