Mô phỏng thuật toán XOR đoạn bằng tiền tố XOR

Subarray XOR via Prefix · Nhóm: Bit & Mặt nạ

Dựng mảng tiền tố XOR pre với pre[0]=0, pre[i]=pre[i-1]^a[i-1], khi đó XOR của đoạn a[l..r] = pre[r+1] ^ pre[l] trong O(1).

Ý tưởng

Khởi tạo pre[0] = 0 (XOR của đoạn rỗng).

Dựng pre[i] = pre[i-1] ^ a[i-1] cho mọi i, được tiền tố XOR chạy dồn.

Trả lời truy vấn đoạn a[l..r] bằng pre[r+1] ^ pre[l]; các tiền tố chồng lấn a[0..l-1] triệt tiêu.

Vì sao đúng

Nhờ x ^ x = 0, phần tiền tố chung của pre[r+1] và pre[l] tự huỷ, chỉ còn lại XOR của đúng đoạn cần tìm; mỗi truy vấn chỉ một phép XOR sau khi dựng tiền tố O(n).

Mã Python

def build_prefix(a):
    pre = [0] * (len(a) + 1)      # pre[0] = 0
    for i in range(1, len(a) + 1):
        pre[i] = pre[i - 1] ^ a[i - 1]   # running XOR
    return pre
def query(pre, l, r):    # XOR of a[l..r]
    return pre[r + 1] ^ pre[l]   # overlapping prefixes cancel

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