Mô phỏng thuật toán Mảng hiệu (Difference Array)

Difference Array · Nhóm: Mảng

Cộng một giá trị lên cả một đoạn [l,r] chỉ bằng cách chạm hai vị trí, thay vì sửa từng phần tử.

Ý tưởng

Dùng mảng hiệu diff cỡ n+1, ban đầu toàn số 0.

Để cộng +v lên đoạn [l,r], làm diff[l] += v và diff[r+1] -= v · mỗi cập nhật chỉ O(1).

Sau khi làm hết mọi cập nhật, lấy tổng tiền tố của diff để dựng lại mảng cuối trong một lượt O(n).

Vì sao đúng

Nhiều cập nhật đoạn trên cùng một mảng · mỗi lần chỉ tốn O(1) thay vì O(độ dài đoạn), rồi dựng lại một lần duy nhất.

Mã Python

def update(diff, l, r, v):     # add v to a[l..r] in O(1)
    diff[l] += v
    diff[r + 1] -= v
def build(diff, n):            # reconstruct by prefix sum
    out = [0] * n
    out[0] = diff[0]
    for i in range(1, n):
        out[i] = out[i - 1] + diff[i]
    return out

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