Lesson 15 — Prefix Sum & Difference Array

3 module tương tác: (1) Prefix sum 1D — dựng mảng P từng bước, truy vấn range sum bằng P[r+1]−P[l]; (2) Difference array — thêm range update O(1), prefix để lấy mảng cuối; (3) Prefix sum 2D — truy vấn submatrix bằng bù trừ 4 góc.

Module 1 — Prefix sum 1D & range query

Mảng a (cách nhau bởi dấu cách):

Mảng a

Prefix sum P (dài n+1, P[0]=0)

l = r =

sum(l, r) = P[r+1] − P[l]

Nhập mảng, dựng P, rồi chọn l, r để xem công thức highlight.

🟧 cam = phần tử trong đoạn [l,r]; 🟩 xanh = P[r+1] (cộng); 🟥 đỏ = P[l] (trừ).

Module 2 — Difference array (range update)

n =

l = r = v =

Difference array d (dài n+1)

Mảng kết quả a (sau prefix)

Thêm vài update rồi bấm "Prefix" để xem mảng cuối.

Mỗi update chỉ chạm 2 ô: 🟩 d[l] += v, 🟥 d[r+1] −= v (O(1)). Prefix sum d → mảng cuối.

Module 3 — Prefix sum 2D (region sum, inclusion-exclusion)

Ma trận m 3×3 cố định. Chọn submatrix (r1,c1)→(r2,c2); xem 4 góc của bảng P được dùng để bù trừ.

r1= c1= r2= c2=

Ma trận m (3×3)

Prefix 2D — P (4×4), highlight 4 góc

sum = P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1]

Chọn submatrix rồi tính.

ô trong submatrix góc cộng (+) góc trừ (−)