Sparse Table "Thực Chiến" - Hé Lộ Các "Tuyệt Kỹ"

Chào mừng anh em đã quay trở lại! Ở phần 1, chúng ta đã "mổ xẻ" lý thuyết về Sparse Table. Giờ là lúc "lăn vào bếp", cụ thể là "xào nấu" code C++ và khám phá những "chiêu thức" lợi hại hơn của "em nó"!

1. "Xắn Tay Áo Lên": Xây Dựng Và Truy Vấn Bằng C++ (Những Nét Cơ Bản)

1.1. Dựng "Sân Khấu": Bảng st Và Các Phép Tính Logarit "Thần Tốc"

Ngôi sao của chúng ta là mảng 2 chiều st[i][j]. Như đã "nhá hàng", st[i][j] sẽ lưu trữ câu trả lời đã được tính toán trước cho đoạn mảng bắt đầu từ chỉ số i và kéo dài $2^j$ phần tử (tức là, arr[i] đến arr[i + (1<<j) - 1]). Giá trị tối đa cho j (gọi là K_MAX_LOG) cần phải sao cho $2^{\text{K\_MAX\_LOG}}$ ít nhất bằng N (kích thước mảng). Ví dụ, với N lên đến $10^5$, K_MAX_LOG sẽ khoảng 16-17.

Chi tiết triển khai C++:

const int MAXN_ARR = 100005; // Kích thước mảng tối đa có thể
const int K_MAX_LOG = 17; // Log tối đa cho MAXN_ARR (floor(log2(MAXN_ARR)))
// Đối với Truy vấn Min Đoạn, lưu trữ giá trị thực tế:
int st[MAXN_ARR][K_MAX_LOG + 1]; // Hoặc nếu N lớn hơn, có thể cần cấp phát động
// int arr[MAXN_ARR]; // Mảng gốc

Tiền xử lý Logarit: Chúng ta sẽ thường xuyên cần $\lfloor \log_2(\text{length\_of\_range}) \rfloor$. Tính toán " chay" bằng log2 liên quan đến toán học dấu phẩy động và có thể "ì ạch" nếu làm nhiều lần. "Tiền xử lý là vua!" Mẹo kinh điển là: lg[1] = 0; for (int i = 2; i <= N; ++i) lg[i] = lg[i/2] + 1;

Mã C++ để tiền xử lý logarit:

int lg[MAXN_ARR + 1]; // Để lưu trữ các giá trị log đã tiền xử lý void precomputeForSt(int n)
{ lg[1] = 0; // log2(1) = 0 for (int i = 2; i <= n; ++i) lg[i] = lg[i/2] + 1;
}
// Cách khác để tính toán tại thời điểm truy vấn bằng hàm nội tại của GCC/Clang:
// int k = (length == 0) ? -1 : 31 - __builtin_clz(length); // Đối với int 32-bit
// C++20 cung cấp bit_width:
// int k = (length == 0) ? -1 : bit_width(static_cast<unsigned int>(length)) - 1;

Tại sao lại tiền xử lý logarit? Bởi vì bắt CPU của anh em thực hiện phép tính $\log_2$ và floor dấu phẩy động mỗi khi truy vấn giống như yêu cầu một con ốc sên thắng một cuộc đua F1 vậy. Thay vào đó, chúng ta đưa cho nó một "tờ cheat sheet" (mảng lg)!

Tiền xử lý Logarit - Một Bước Nhỏ Cho Code, Một Bước Tiến Lớn Cho Tốc Độ Truy Vấn. Việc tính toán $k=\lfloor\log_2(\text{length})\rfloor$ là "trái tim" của mọi truy vấn. Mặc dù log2 có sẵn, nó hoạt động trên số thực, và các thao tác floor và chuyển đổi sang int sau đó sẽ thêm chi phí. Đối với một cấu trúc dữ liệu "tự hào" về truy vấn $O(1)$, việc tính toán lặp đi lặp lại này có thể trở thành "nút thắt cổ chai", đặc biệt là trong lập trình thi đấu với giới hạn thời gian "eo hẹp" và hàng triệu truy vấn. Việc tiền xử lý mảng lg chỉ mất $O(N)$ thời gian một lần. Sau đó, việc lấy lg[length] là một thao tác tra cứu mảng $O(1)$ thực sự. Tối ưu hóa có vẻ nhỏ này đảm bảo phần truy vấn vẫn thực sự là hằng số thời gian.

1.2. Xây Dựng Sparse Table (Tiền Xử Lý - $O(N \log N)$ "Thần Thánh")

Khai báo hàm (ví dụ, cho RMQ): void buildRMQSt(const vector<int>& arr) Trường hợp cơ sở ($j=0$): Đối với các đoạn có độ dài $2^0=1$, câu trả lời chính là bản thân phần tử đó. Vậy, st[i][0] = arr[i].

Vòng lặp ngoài (cho j, đại diện cho $2^j$): for (int j = 1; j <= K_MAX_LOG; ++j) (trong đó K_MAX_LOG là lg[n]). Vòng lặp trong (cho i, chỉ số bắt đầu): for (int i = 0; i + (1 << j) <= n; ++i). Giới hạn vòng lặp này rất quan trọng: i + (1 << j) là chỉ số đầu tiên sau khối hiện tại có độ dài $2^j$. Vì vậy, i + (1 << j) <= n có nghĩa là khối đó "vừa vặn".

Công thức truy hồi: st[i][j] = operation(st[i][j-1], st[i + (1 << (j-1))][j-1]);. Đối với RMQ, công thức này là st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1]);.

Ví dụ đầy đủ về xây dựng RMQ bằng C++:

// Giả sử MAXN_ARR, K_MAX_LOG, st, lg được khai báo toàn cục hoặc trong một lớp
// void precomputeForSt(int n) đã được định nghĩa void buildRMQSt(const vector<int>& arr) { int n = arr.size(); if (n == 0) return; // precomputeForSt(n); // Gọi hàm này một lần, có thể ở bên ngoài nếu n cố định // Trường hợp cơ sở: j = 0 (các đoạn có độ dài 2^0 = 1) for (int i = 0; i < n; ++i) st[i][0] = arr[i]; // Điền cho j = 1 đến K_MAX_LOG (hoặc lg[n]) // K_MAX_LOG phải ít nhất bằng lg[n] for (int j = 1; (1 << j) <= n; ++j) // Lặp j khi 2^j là độ dài hợp lệ for (int i = 0; i + (1 << j) <= n; ++i) st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1]);
}

1.3. Truy Vấn Với Các Phép Toán Idempotent ($O(1)$ - "Quả Ngọt" Hái Liền Tay!)

Khai báo hàm (ví dụ, cho RMQ): int queryRMEFromSt(int L, int R) (giả sử đoạn [L,R] được đánh chỉ số từ 0). Tính độ dài: int length = R - L + 1; Tìm k (lũy thừa lớn nhất của 2 sao cho $2^k \le \text{length}$): int k = lg[length]; (sử dụng mảng lg đã tiền xử lý của chúng ta).

"Mánh Khóe" $O(1)$: Câu trả lời là operation(st[L][k], st[R - (1 << k) + 1][k]). Đối với RMQ: min(st[L][k], st[R - (1 << k) + 1][k]);.

Giải thích R - (1 << k) + 1: Đây là chỉ số bắt đầu của đoạn thứ hai. Đoạn này có độ dài (1 << k) và nó kết thúc chính xác tại R. Vì vậy, chỉ số bắt đầu của nó là R - (length_of_segment - 1) = R - ((1<<k) - 1) = R - (1<<k) + 1.

Ví dụ đầy đủ về truy vấn RMQ bằng C++:

int queryRMQFromSt(int L, int R) { // Đảm bảo L và R hợp lệ và L <= R if (L < 0 || R >= MAXN_ARR || L > R) // MAXN_ARR là kích thước tối đa của mảng gốc { // Xử lý lỗi: trả về vô cực, ném ngoại lệ, v.v. return 2e9; // Giá trị đại diện cho "vô cực" } int length = R - L + 1; if (length == 0) return 2e9; // Hoặc xử lý đoạn rỗng int k = lg[length]; // Sử dụng log đã tiền xử lý return min(st[L][k], st[R - (1 << k) + 1][k]);
}

Truy vấn này nhanh đến mức, nó giống như Flash hỏi hai người bạn siêu nhanh của mình, những người đã "do thám" các phần của phạm vi. Một người nhìn từ L trong $2^k$ bước. Người kia tự định vị sao cho $2^k$ bước của họ kết thúc chính xác tại R. Họ báo cáo lại, Flash lấy min, và mọi việc hoàn thành trước khi anh em kịp chớp mắt! Phần chồng chéo ư? Min không quan tâm! Đó chính là idempotence "thần thánh"!

2. Vượt Ra Ngoài Min/Max: Mở Rộng "Siêu Năng Lực" Sparse Table

2.1. Truy Vấn GCD/LCM Trong Đoạn (Vẫn Là $O(1)$ Và Các "Anh Hùng" Idempotent!)

Phép toán Ước Chung Lớn Nhất (GCD) có tính kết hợp và idempotent (gcd(x,x)=x). Do đó, Sparse Table có thể tìm GCD của một đoạn trong thời gian $O(1)$ cho mỗi truy vấn, sử dụng logic xây dựng và truy vấn giống hệt như RMQ, chỉ cần thay thế min bằng gcd. Bội Chung Nhỏ Nhất (LCM) của một đoạn cũng có thể được xử lý tương tự nếu lcm(x,x)=x và nó có tính kết hợp, nhưng cần cẩn thận về khả năng tràn số nếu các số quá lớn. Cấu trúc truy vấn vẫn giữ nguyên.

Mã C++ cho GCD Đoạn: (Cấu trúc giống hệt RMQ; chỉ cần thay đổi phép toán)

// Giả sử stGcd[MAXN_ARR][K_MAX_LOG + 1] đã được khai báo
// void precomputeForSt(int n) có sẵn
// int lg[MAXN_ARR + 1] đã được tiền xử lý
int stGcd[MAXN_ARR][K_MAX_LOG + 1]; // Khai báo bảng stGcd // GCD tùy chỉnh cho C++ cũ hơn hoặc nhu cầu cụ thể
int calcGcd(int a, int b)
{ return gcd(a, b); // C++17 // while (b) { a %= b; swap(a, b); } return a; // Thủ công
} void buildGcdSt(const vector<int>& arr)
{ int n = arr.size(); if (n == 0) return; // precomputeForSt(n); // Đảm bảo log đã sẵn sàng for (int i = 0; i < n; ++i) stGcd[i][0] = arr[i]; for (int j = 1; (1 << j) <= n; ++j) for (int i = 0; i + (1 << j) <= n; ++i) stGcd[i][j] = calcGcd(stGcd[i][j-1], stGcd[i + (1 << (j-1))][j-1]);
} int queryGcdFromSt(int L, int R)
{ if (L < 0 || R >= MAXN_ARR || L > R) return 0; // GCD của tập rỗng khá phức tạp, thường dùng 0 int length = R - L + 1; if (length == 0) return 0; int k = lg[length]; return calcGcd(stGcd[L][k], stGcd[R - (1 << k) + 1][k]);
}

Cần tìm "sự đồng thuận chung lớn nhất" trong một loạt các con số? GCD và Sparse Table "song kiếm hợp bích" để giải quyết vấn đề trong $O(1)$! Cứ như thể họ là "phái đoàn ngoại giao tối thượng" cho mảng của anh em vậy.

2.2. Truy Vấn Tổng/Tích Trong Đoạn (Cuộc Phiêu Lưu $O(\log N)$ - Khi Idempotence "Đi Vắng")

Tổng và Tích có tính kết hợp ((a+b)+c = a+(b+c)) nhưng quan trọng là không idempotent (a+a != a nói chung). Điều này có nghĩa là "mánh" các khối chồng chéo $O(1)$ sẽ "phá sản" vì nó sẽ dẫn đến việc đếm trùng (đối với tổng) hoặc lũy thừa sai (đối với tích). Vì vậy, đối với những phép toán này, thời gian truy vấn trở thành $O(\log N)$. Chúng ta đạt được điều này bằng cách phân rã đoạn truy vấn [L,R] thành tối đa $\log N$ khối không giao nhau, mỗi khối có độ dài là một lũy thừa của hai.

Xây dựng stSum / stProd: Quá trình xây dựng tương tự: st_op[i][0] = arr[i]. Công thức truy hồi trở thành stSum[i][j] = stSum[i][j-1] + stSum[i + (1<<(j-1))][j-1]. Đối với tích: stProd[i][j] = stProd[i][j-1] * stProd[i + (1<<(j-1))][j-1]. (Xử lý toán học modulo nếu tích quá lớn, và cẩn thận với số không).

Logic truy vấn (Lặp cho $O(\log N)$): Ý tưởng là lặp từ lũy thừa lớn nhất của hai xuống. Nếu một khối có kích thước $2^j$ bắt đầu từ L hiện tại vừa với đoạn còn lại, chúng ta kết hợp st_op[L][j] vào câu trả lời của mình và tăng L lên $2^j$.

Ví dụ đầy đủ về Tổng Đoạn bằng C++:

long long stSum[MAXN_ARR][K_MAX_LOG + 1]; // Sử dụng long long cho tổng
// void precomputeForSt(int n) có sẵn
// int lg[MAXN_ARR + 1] đã được tiền xử lý void buildSumSt(const vector<long long>& arr) // Sử dụng long long cho tổng
{ int n = arr.size(); if (n == 0) return; // precomputeForSt(n); for (int i = 0; i < n; ++i) stSum[i][0] = arr[i]; for (int j = 1; (1 << j) <= n; ++j) for (int i = 0; i + (1 << j) <= n; ++i) stSum[i][j] = stSum[i][j-1] + stSum[i + (1 << (j-1))][j-1];
} long long querySumFromSt(int L, int R)
{ if (L < 0 || R >= MAXN_ARR || L > R) // Tổng của đoạn rỗng/không hợp lệ return 0; long long curSum = 0; // Lặp xuống từ lũy thừa lớn nhất của 2 có thể vừa (K_MAX_LOG hoặc lg[R-L+1]) for (int j = K_MAX_LOG; j >= 0; --j) { if (L + (1 << j) - 1 <= R) { // Nếu một khối kích thước 2^j bắt đầu từ L vừa trong [R-L+1] curSum += stSum[L][j]; L += (1 << j); // Di chuyển L đến đầu đoạn tiếp theo } } return curSum;
}

Truy Vấn Tích Đoạn (RPQ): Logic tương tự như RSQ (Range Sum Query). Xây dựng bảng với stProd[i][j] = stProd[i][j-1] * stProd[i + (1<<(j-1))][j-1]. Truy vấn lặp, nhân kết quả từ các khối không giao nhau. Thận trọng: Cẩn thận với tích trở nên quá lớn (sử dụng long long hoặc modulo) hoặc tích liên quan đến số không. Nếu có số không trong đoạn, tích bằng không (trừ khi đoạn rỗng hoặc có quy tắc cụ thể áp dụng).

Tổng và Tích giống như những người bạn phải có "không gian riêng". Không được phép chồng chéo, nếu không họ sẽ bắt đầu một cuộc "cãi vã" (bằng cách đếm gấp đôi). Vì vậy, chúng ta cho họ những "căn phòng" riêng biệt có kích thước $\log N$. Truy vấn $O(\log N)$ cho các phép toán kết hợp không idempotent là hệ quả trực tiếp của việc cần các khoảng không giao nhau.

3. "Phép Thuật" Cao Cấp: Sparse Table Giải Quyết Vấn Đề "Khó Nhằn"

3.1. Tổ Tiên Chung Gần Nhất (LCA) Trong Cây - "Dịch Chuyển Tức Thời" Với Euler Tour!

Bài toán LCA có thể được quy về một phiên bản giới hạn của bài toán RMQ. Kỹ thuật Euler Tour... Nếu chúng ta thay thế segment tree tính toán min bằng sparse table, thì chúng ta tiền xử lý trong thời gian $O(N \log N)$ và truy vấn trong thời gian $O(1)$.

Giải thích "sơ sơ":

1. Thực hiện một chuyến đi Euler (Euler tour) của cây.
2. Lưu trữ:
   • eulerNodes: Dãy các nút được thăm.
   • eulerDepth: Độ sâu của mỗi nút trong eulerNodes.
   • firstOccurrence[node]: Chỉ số lần xuất hiện đầu tiên của node trong eulerNodes.
3. LCA của hai nút u và v là nút có độ sâu nhỏ nhất trong mảng eulerNodes giữa firstOccurrence[u] và firstOccurrence[v].
4. Xây dựng một Sparse Table trên eulerDepth để tìm chỉ số của độ sâu nhỏ nhất trong $O(1)$.
5. Nút tại chỉ số đó trong eulerNodes chính là LCA của anh em.

Tìm LCA bằng Euler Tour và RMQ giống như thực hiện một "chuyến đi bộ kỳ diệu" qua cái cây, ghi lại anh em nhìn thấy ai và họ ở độ sâu bao nhiêu. Sau đó, để tìm "sếp chung" của hai "nhân viên", anh em chỉ cần tìm người "nông" nhất gặp trên đường đi giữa lần nhìn thấy đầu tiên của họ. Sparse Table làm cho việc tìm "người nông nhất" đó diễn ra "trong một nốt nhạc"!

3.2. Truy Vấn Mảng Tiền Tố Chung Dài Nhất (LCP) - Dành Cho Các "Nhà Giả Kim" Chuỗi Ký Tự

"Để tính LCP(i, j) [LCP của các hậu tố bắt đầu từ chỉ số gốc i và j], chỉ cần tìm vị trí của i và j trong mảng hậu tố [giả sử pos[i] và pos[j]] và tính giá trị nhỏ nhất trong đoạn lcp[min(pos[i], pos[j])+1] đến lcp[max(pos[i], pos[j])]." (Lưu ý: Tài liệu gốc ghi lcp[min(pos[i], pos[j])] đến lcp[max(pos[i], pos[j])-1], nhưng cách tiếp cận phổ biến hơn là query trên đoạn [min_rank+1, max_rank] của mảng LCP khi mảng LCP được định nghĩa là LCP giữa suffix sa[k] và sa[k-1]). Nếu Mảng Hậu tố là sa và mảng LCP là lcp (trong đó lcp[k] là LCP của sa[k] và sa[k-1]), thì LCP của sa[x] và sa[y] (giả sử x < y) là min(lcp[x+1]...lcp[y]).

Giải thích "ngắn gọn": Sau khi xây dựng Mảng Hậu tố (Suffix Array) và mảng LCP (Longest Common Prefix - Tiền tố chung dài nhất giữa các hậu tố liền kề trong mảng hậu tố đã sắp xếp) tương ứng, việc tìm LCP của bất kỳ hai hậu tố nào (không nhất thiết phải liền kề) trở thành một bài toán RMQ trên mảng LCP. LCP của các hậu tố S[sa[i]...] và S[sa[j]...] (trong đó sa là mảng hậu tố, và giả sử rank[sa[i]] < rank[sa[j]]) là min(lcpArr[rank[sa[i]]+1],..., lcpArr[rank[sa[j]]]). Xây dựng một Sparse Table trên mảng LCP để truy vấn LCP $O(1)$ giữa bất kỳ hai hậu tố nào.

Mảng hậu tố và LCP đã giống như "nói một ngôn ngữ chuỗi cổ đại" rồi. Thêm Sparse Table vào giống như "phù phép" ngôn ngữ đó để "dịch tức thời" các tiền tố chung!

3.3. Các "Pha Bẻ Lái" Sáng Tạo Khác (Đề Cập "Sương Sương")

• Tổng XOR Trong Đoạn: XOR có tính kết hợp và xor(x,x)=0. Mặc dù không hoàn toàn idempotent theo nghĩa op(x,x)=x cho truy vấn $O(1)$, các thuộc tính của nó có thể cho phép các biến thể. Truy vấn $O(\log N)$ cho các phép toán kết hợp vẫn "ngon lành".
• AND/OR Bit Trong Đoạn: Các phép toán này là idempotent. AND(x,x)=x, OR(x,x)=x. Vì vậy, truy vấn $O(1)$ "chạy tốt".

Sparse Table: Không chỉ dành cho min/max đâu nha! Chúng bí mật "đi làm thêm" với tổng XOR và các "anh em bạn dì" bitwise nữa đấy.

4. "Đại Chiến" Tay Ba: Sparse Table vs. Segment Tree vs. Fenwick Tree

4.1. "Điểm Mặt Anh Tài": Giới Thiệu Nhanh Các "Đấu Sĩ"

• Segment Tree: "Vận động viên" toàn năng, linh hoạt. Xử lý các truy vấn đoạn và cập nhật. Ví von: "Dao đa năng Thụy Sĩ".
• Fenwick Tree (BIT): Chuyên gia về tổng tiền tố và cập nhật điểm. Nhanh và gọn. Ví von: "Đứa trẻ trầm lặng gây ngạc nhiên với kỹ năng toán học" hoặc một công cụ được "mài dũa" cho các tác vụ liên quan đến tổng cụ thể.
• Sparse Table: Anh hùng của chúng ta hôm nay – "tay đua" mảng tĩnh cho các truy vấn idempotent. Ví von: "Báo Gêpa đi giày trượt patin" hoặc "tờ cheat sheet được chuẩn bị sẵn".

4.2. Bảng So Sánh "Một Chín Một Mười"

Nguyên Tắc "Không Có Bữa Trưa Miễn Phí" Trong Cấu Trúc Dữ Liệu. Bảng so sánh cho thấy rõ ràng các sự "được-mất". Sparse Table có truy vấn $O(1)$ cho một số phép toán nhưng "hy sinh" khả năng cập nhật động và "ngốn" nhiều không gian hơn. Segment Tree linh hoạt nhưng truy vấn là $O(\log N)$. Fenwick Tree "nhẹ nhàng" và tốt cho tổng nhưng ít "đa năng" hơn Segment Tree.

4.3. Giờ Quyết Định! Khi Nào "Triệu Hồi" Nhà Vô Địch Nào?

• Sparse Table: Mảng tĩnh, cần "cày" hàng tấn truy vấn RMQ/GCD "nhanh như điện".
• Segment Tree: Mảng "thay hình đổi dạng", hoặc anh em cần cập nhật đoạn, hoặc các phép toán đoạn "xoắn não" hơn min/max/gcd/sum.
• Fenwick Tree: Anh em cần tổng đoạn/tổng tiền tố và cập nhật điểm, và muốn một cái gì đó "đơn giản"/tiết kiệm không gian hơn Segment Tree.

Chọn lựa giữa chúng giống như chọn Pokémon: Sparse Table là Pikachu "tốc độ" của anh em cho các trận chiến tĩnh cụ thể, Segment Tree là Eevee "linh hoạt biến hóa", và Fenwick Tree là Geodude "hiệu quả" cho công việc liên quan đến tổng.

5. Mẹo "Pro", "Tricks" Hay Và Né "Gremlin" C++

5.1. Kinh Nghiệm "Xương Máu" & Tối Ưu Hóa

• Hằng số: Định nghĩa rõ ràng MAXN và K (giá trị log tối đa). K có thể là $\lfloor \log_2(\text{MAXN}) \rfloor$ hoặc "nhỉnh" hơn một chút cho "an tâm".
• Tiền xử lý Logarit: Đã nói rồi nhưng vẫn phải "nhấn mạnh" tầm quan trọng của nó đối với truy vấn $O(1)$ "thần thánh".
• Đánh chỉ số từ 0 vs. từ 1: Hãy "nhất quán"! Hầu hết các ví dụ C++ dùng chỉ số từ 0. Nếu bài toán dùng chỉ số từ 1, hãy "cẩn thận từng li từng tí" khi điều chỉnh.
• Quản lý bộ nhớ (C++): vector<vector<int>> st; là "bạn hiền" để định kích thước động nếu N không cố định lúc biên dịch, hoặc xài mảng toàn cục nếu N bị giới hạn.
• Tối ưu hóa cho N nhỏ: Nếu N "bé xíu", Sparse Table có thể là "dao mổ trâu giết gà". "Trâu bò" (brute force) hoặc DP đơn giản hơn có khi lại "ngon".

5.2. Các Lỗi C++ "Trời Ơi Đất Hỡi" & Cách "Diệt" Chúng (Như Một "Thợ Săn Bọ" Lập Trình!)

• Nỗi Kinh Hoàng Off-by-One: "Các vòng lặp thường chứa lỗi off-by-one... đặt sai giới hạn vòng lặp". "Lỗi này ở đây là một lỗi rất phổ biến... được gọi là lỗi off-by-one, nó phổ biến đến mức có cả tên riêng." Đây là một cạm bẫy "TO ĐÙNG" trong lập trình thi đấu nói chung, và Sparse Table cũng không "thoát nạn".
  • Cụ thể với Sparse Table:
    • Độ dài đoạn: R - L + 1, không phải R - L.
    • Vòng lặp cho j khi xây dựng: j <= K hoặc (1 << j) <= n. Nếu j quá cao, 1 << j sẽ "toang" (tràn số) hoặc i + (1 << (j-1)) sẽ "bay" ra ngoài biên.
    • Vòng lặp cho i khi xây dựng: i + (1 << j) <= n. Nếu là i < n - (1 << j) + 1, nó tương đương. Nhưng i < n - (1 << j) là "sai bét".
    • Truy vấn: st[R - (1 << k) + 1][k]. Quên +1 là một lỗi "kinh cmn điển".
• Sự Cố Tính Toán Logarit:
  • Sử dụng log2 từ <cmath> trả về một số double; nhớ floor() và ép kiểu sang int. Việc tiền xử lý lg[length] "né" được vụ này.
  • log2(0) hoặc log2(1): lg[1] phải là 0. Đảm bảo length luôn ít nhất là 1.
  • __builtin_clz(0) không xác định. Xử lý length = 0 hoặc length = 1 cẩn thận nếu dùng nó.
• Ác Mộng Đánh Chỉ Số Mảng (trong st[MAXN][K+1]):
  • st[i + (1 << (j-1))][j-1]: Đảm bảo i + (1 << (j-1)) nằm trong [0, n-1]. Điều kiện vòng lặp xây dựng i + (1 << j) <= n sẽ ngăn chặn điều này cho số hạng đầu tiên st[i][j-1], và cũng cho số hạng thứ hai st[i + (1<<(j-1))][j-1] vì i + (1<<(j-1)) + (1<<(j-1)) = i + (1<<j).
  • Truy vấn: st[L][k] và st[R - (1 << k) + 1][k]. Đảm bảo L và R - (1 << k) + 1 là các chỉ số hợp lệ. L, R phải nằm trong [0, n-1].
• Quên Quy Tắc Idempotence/Tính Kết Hợp: Xài truy vấn $O(1)$ cho tổng là "toang".

Lỗi off-by-one: những "ninja tí hon" phá hoại code của anh em. Chúng ta sẽ học các "chiêu trò lén lút" của chúng! Còn tính toán logarit? Sai một ly, truy vấn của anh em có thể "lạc trôi" đến Narnia.

5.3. Ví Dụ Code C++ "Bá Đạo" (Vượt Ra Ngoài Những Điều "Hiển Nhiên")

• RMQ lưu trữ cặp {value, index}: Để lấy không chỉ giá trị min mà còn cả "tung tích" (chỉ số gốc) của nó. Phép toán min sẽ so sánh giá trị, sau đó "phân xử" hòa bằng chỉ số.

  struct Node
  { int value; int index; // Nạp chồng toán tử < để so sánh Node, ưu tiên value rồi đến index bool operator<(const Node& other) const { if (value != other.value) return value < other.value; return index < other.index; // Phá vỡ thế hòa bằng chỉ số nhỏ hơn }
  };
  // Node st_pair[MAXN_ARR][K_MAX_LOG + 1]; // Việc xây dựng và truy vấn sẽ sử dụng Node và toán tử < tùy chỉnh
  

• Sparse Table 2D (Khái Niệm "Lướt Qua"): Nếu "thời gian/không gian cho phép", có thể đề cập khái niệm này mở rộng sang 2D cho RMQ 2D, dù tiền xử lý "khủng khiếp" hơn: $O(N \cdot M \cdot \log N \cdot \log M)$.

Muốn biết giá trị nhỏ nhất và nó "lòi" ra từ đâu? Chúng ta sẽ làm cho Sparse Table "khai ra"! Sparse Table 2D ư? Đó giống như xây dựng một "tòa nhà chọc trời" bằng các bảng tra cứu – "ấn tượng" đấy, nhưng hãy "cẩn thận khi sử dụng". Hẹn anh em một bài gần nhất với Sparse Table 2D nhé!

6. Kết Luận: Anh Em Đã "Lên Trình" Sparse Table Rồi Đấy! (Hầu Hết Là Vậy)

6.1. Tóm Tắt "Siêu Năng Lực":

• Truy vấn $O(1)$ "nhanh như chớp" cho các phép toán tĩnh, idempotent (RMQ, GCD).
• Truy vấn $O(\log N)$ hiệu quả cho các phép toán tĩnh, kết hợp (RSQ, Tích).
• Ứng dụng "đa-zi-năng" (LCA, LCP).

6.2. Lời Khuyên "Tâm Huyết":

"Hãy nhớ, với sức mạnh lớn lao (của lũy thừa hai) đi kèm trách nhiệm lớn lao (kiểm tra giới hạn mảng của bạn)!" Khuyến khích anh em luyện tập.

Dưới đây là một số đấu trường nơi bạn có thể rèn luyện kỹ năng Sparse Table của mình:

Range Minimum Query (RMQ) cơ bản:

• Library Checker - Static RMQ
• Codechef - FRMQ (Chef and Array)
• SPOJ - RMQSQ

Range GCD Query (RGCD):

• Codeforces - 475D (CGCDSSQ)
  (Bài này yêu cầu đếm số cặp (L,R) có GCD bằng một giá trị cụ thể, có thể dùng Sparse Table để tối ưu việc tính GCD cho mỗi đoạn)

Ứng dụng LCA (Lowest Common Ancestor):

• SPOJ - DISQUERY
  (Tính toán trên đường đi giữa u và v, LCA là một phần quan trọng)
• CodeChef - TALCA
  (Thay đổi gốc của cây và tìm LCA mới)
• CSES - Company Queries II
  (Tìm LCA)

Các bài toán kết hợp khác:

• Codeforces - 5C (Longest Regular Bracket Sequence)
  (Có thể dùng RMQ trên mảng prefix sum của dấu ngoặc để tìm đoạn con hợp lệ dài nhất)
• Codeforces - 1454F (Array Partition)
  (Tìm cách chia mảng thành 3 phần sao cho max(phần1) = min(phần2) = max(phần3), RMQ/RMaxQ rất hữu ích)
• Codeforces - 487B (Strip)
  (Bài toán DP kết hợp RMQ để kiểm tra điều kiện trên các đoạn con)
• VNOJ - AVLBIT (Dãy cấp số cộng)
  (Có thể có những cách tiếp cận sử dụng cấu trúc dữ liệu đoạn)

Chúc anh em code vui và "bá đạo" hơn mỗi ngày!