2D Prefix Sum · Nhóm: Cấu trúc dữ liệu
Tổng tiền tố 2D dựng sẵn một bảng dồn tích trên ma trận để mọi truy vấn tổng một hình chữ nhật con chỉ cần đọc bốn ô góc rồi cộng trừ theo nguyên lý bao-trừ.
Thêm một hàng và một cột đệm bằng 0 rồi điền bảng P theo từng ô: lấy giá trị hiện tại cộng ô trên cộng ô trái trừ ô góc trên-trái bị đếm đôi.
Sau khi dựng, bảng P lưu tổng của mọi hình chữ nhật tính từ góc trên-trái.
Truy vấn một vùng lấy ô góc phải-dưới trừ hai dải thừa rồi cộng bù phần bị trừ hai lần.
Dựng bảng chỉ tốn một lần theo kích thước ma trận, sau đó mỗi truy vấn tổng vùng chỉ đọc bốn ô nên tốn thời gian hằng số bất kể vùng lớn hay nhỏ.
def build_prefix(a, n, m):
P = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1): # build row by row
for j in range(1, m + 1): # inclusion-exclusion
P[i][j] = a[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]
return P
def rect_sum(P, r1, c1, r2, c2): # O(1) query
return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.