Mô phỏng thuật toán Bảng thưa (Sparse Table), RMQ

Sparse Table (RMQ) · Nhóm: Cấu trúc dữ liệu

Bảng thưa (Sparse Table), RMQ (Sparse Table (RMQ)), nhóm Cấu trúc dữ liệu.

Mã Python

def build(a):
    n = len(a)
    K = n.bit_length()
    for i in range(n):
        table[0][i] = a[i]
    for j in range(1, K):
        for i in range(n - (1<<j) + 1):
            table[j][i] = min(table[j-1][i], table[j-1][i+(1<<(j-1))])
def query(l, r):
    j = (r-l+1).bit_length() - 1
    return min(table[j][l], table[j][r-(1<<j)+1])

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.