Sparse Table: Hướng Dẫn Chi Tiết và Ứng Dụng Thực Tế (JavaScript)

Bạn đang tìm kiếm một cấu trúc dữ liệu hiệu quả để xử lý các truy vấn phạm vi trên mảng tĩnh? Sparse Table chính là giải pháp! Bài viết này cung cấp một cái nhìn toàn diện về Sparse Table, từ khái niệm cơ bản đến các ứng dụng thực tế, cùng với ví dụ code JavaScript dễ hiểu. Hãy cùng khám phá sức mạnh của cấu trúc dữ liệu này!

Sparse Table là gì?

Sparse Table là một cấu trúc dữ liệu tiền xử lý cho phép trả lời các truy vấn phạm vi trong thời gian O(1) sau khi đã tiền xử lý O(N log N). Điều này làm cho nó trở nên lý tưởng cho các mảng tĩnh, nơi các phần tử không thay đổi sau khi tiền xử lý.

Khi nào nên sử dụng Sparse Table?

• Khi bài toán liên quan đến các truy vấn phạm vi tĩnh (không có cập nhật).
• Khi thao tác là lũy đẳng (ví dụ: min, max, GCD).
• Khi bạn cần các truy vấn nhanh chóng trong thời gian O(1).
• Khi bạn có thể chấp nhận thời gian tiền xử lý O(N log N) và không gian O(N log N).

Cách hoạt động của Sparse Table

Sparse Table lưu trữ các kết quả đã tính toán trước cho các mảng con chồng lấn có độ dài là lũy thừa của hai. Sử dụng thông tin đã tính toán trước này, chúng ta có thể trả lời các truy vấn trong thời gian hằng số. Chúng ta định nghĩa `st[i][j]`, trong đó:

• `i` đại diện cho chỉ số bắt đầu của phạm vi.
• `j` đại diện cho độ dài của mảng con là 2^j (lũy thừa của hai).

Ví dụ: nếu `j = 3`, kích thước phạm vi là 2^3 = 8, có nghĩa là `st[i][3]` lưu trữ kết quả cho phạm vi `[i, i + 7]`.

Xây dựng Sparse Table

Chúng ta điền `st[i][j]` dựa trên thuộc tính lũy đẳng: st[i][j] = operation(st[i][j-1], st[i + 2^(j-1)][j-1]) Công thức này đảm bảo rằng mọi khoảng đều được xây dựng bằng cách sử dụng hai khoảng nhỏ hơn đã được tính toán trước đó.

Triển khai Sparse Table (Truy Vấn Tìm Giá Trị Nhỏ Nhất)

Bây giờ, hãy triển khai một Sparse Table cho Truy Vấn Tìm Giá Trị Nhỏ Nhất (RMQ).

        
class SparseTable {
    constructor(arr) {
        this.n = arr.length;
        this.log = new Uint8Array(this.n + 1);
        this.st = Array.from({ length: this.n }, () => new Int32Array(20));

        // Compute logarithm values
        for (let i = 2; i <= this.n; i++) this.log[i] = this.log[i >> 1] + 1;

        // Initialize Sparse Table with original array values
        for (let i = 0; i < this.n; i++) this.st[i][0] = arr[i];

        // Fill the table
        for (let j = 1; (1 << j) <= this.n; j++) {
            for (let i = 0; i + (1 << j) <= this.n; i++) {
                this.st[i][j] = Math.min(this.st[i][j - 1], this.st[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    // Query for minimum in range [L, R]
    query(L, R) {
        let j = this.log[R - L + 1];
        return Math.min(this.st[L][j], this.st[R - (1 << j) + 1][j]);
    }
}

// Usage
let arr = [1, 3, 5, 7, 9, 2, 6, 4, 8, 0];
let st = new SparseTable(arr);
console.log(st.query(2, 5)); // Output: 2
console.log(st.query(0, 9)); // Output: 0
        
    

Truy vấn Sparse Table

Đối với một phạm vi cho trước `[L, R]`, chúng ta sử dụng đoạn lũy thừa của hai lớn nhất phù hợp với phạm vi. Điều này có nghĩa là: answer = min(st[L][j], st[R - 2^j + 1][j]) trong đó: j = floor(log2(R - L + 1)) Chúng ta sử dụng hai khoảng chồng lấn để bao phủ toàn bộ phạm vi.

Tại sao Truy Vấn Mất O(1)?

Vì chúng ta chỉ thực hiện hai lần tra cứu và một thao tác `Math.min()`, độ phức tạp thời gian là O(1).

Độ Phức Tạp Thời Gian và Không Gian

• Xây dựng Bảng: O(n log n)
• Truy Vấn: O(1)
• Độ Phức Tạp Không Gian: O(n log n)

Sparse Table cực kỳ hiệu quả cho các truy vấn phạm vi tĩnh, nhưng không phù hợp cho các bài toán yêu cầu sửa đổi.

Ví Dụ Về Sparse Table trong Thực Tế

Ví dụ 1: Truy Vấn Tìm Giá Trị Lớn Nhất

Chúng ta thay thế `Math.min()` bằng `Math.max()`, và việc triển khai vẫn giữ nguyên.

Ví dụ 2: Truy Vấn Tìm Ước Số Chung Lớn Nhất

Thay vì min/max, chúng ta sử dụng `gcd(a, b)`:

        
function gcd(a, b) {
    while (b) [a, b] = [b, a % b];
    return a;
}
        
    

Sau đó, thay thế `Math.min()` trong tính toán `st[i][j]` bằng `gcd()`.

So Sánh giữa Segment Tree và Sparse Table

Sparse Table chiến thắng khi:

• Bạn có dữ liệu tĩnh (không có cập nhật).
• Bạn cần các truy vấn nhanh (O(1) so với O(log N) trong Segment Tree).

Kết luận

Sparse Table siêu hiệu quả để trả lời các truy vấn phạm vi khi không cần cập nhật. Bằng cách tính toán trước các đoạn lũy thừa của hai, chúng ta đảm bảo các truy vấn có thể được trả lời trong thời gian hằng số.

Những Điểm Chính Cần Nhớ:

• Tiền xử lý trong O(n log n), Truy vấn trong O(1).
• Chỉ hoạt động cho các thao tác lũy đẳng như min, max, GCD.
• Không phù hợp cho các bài toán yêu cầu cập nhật.
• Tốt hơn Segment Tree cho các truy vấn tĩnh.

Hãy thử triển khai Sparse Table cho các bài toán khác nhau như:

• Truy Vấn LCM
• Truy Vấn Bitwise AND
• Truy Vấn Tổng (với một chỉnh sửa nhỏ)

Bằng cách làm chủ Sparse Table, bạn mở khóa một kỹ thuật mạnh mẽ để truy vấn phạm vi nhanh chóng trong lập trình cạnh tranh!

Chúc bạn coding vui vẻ!