Mô phỏng thuật toán Chia căn (Sqrt Decomposition)

Sqrt Decomposition · Nhóm: Cấu trúc dữ liệu

Chia căn (Sqrt Decomposition) chia mảng thành các khối cỡ căn n và lưu sẵn tổng mỗi khối, nhờ đó tổng một đoạn chỉ cần cộng vài tổng-khối cùng ít phần tử lẻ ở hai đầu.

Ý tưởng

Chia mảng n phần tử thành các khối liên tiếp mỗi khối cỡ khoảng căn n và tính sẵn tổng của từng khối.

Với truy vấn đoạn, các khối nằm trọn trong đoạn thì cộng thẳng tổng-khối đã lưu.

Hai đầu đoạn còn lẻ thì cộng bù từng phần tử một cách riêng lẻ.

Vì sao đúng

Một đoạn bất kỳ chỉ chạm nhiều nhất khoảng căn n khối cùng hai phần khối lẻ, nên mỗi truy vấn tốn khoảng căn n thao tác thay vì duyệt hết đoạn.

Mã Python

def build(a):
    B = int(len(a) ** 0.5) + 1
    block = [0] * (len(a) // B + 1)
    for i, v in enumerate(a):
        block[i // B] += v
def query(a, block, l, r):   # sum of a[l..r]
    B, s, i = ..., 0, l
    while i <= r:
        if i % B == 0 and i + B - 1 <= r:
            s += block[i // B]; i += B   # whole block
        else:
            s += a[i]; i += 1            # single element
    return s

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