Truy Vấn Tổng Hình Chữ Nhật Con 2D Prefix Sum O(1)

Arrays Buổi 15 — Prefix Sum & Difference Array prefix-sum
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
matrix
Submissions
Đề bài

Cho bảng số kích thước N × M (chỉ số hàng từ 1..N, cột từ 1..M) và Q truy vấn. Mỗi truy vấn gồm 4 số nguyên r1, c1, r2, c2 (1 ≤ r1 ≤ r2 ≤ N, 1 ≤ c1 ≤ c2 ≤ M), yêu cầu tính tổng tất cả các phần tử nằm trong hình chữ nhật con có góc trên trái (r1, c1) và góc dưới phải (r2, c2).

Dữ liệu vào (Input)
  • Dòng 1: Ba số nguyên dương N, M, Q (1 ≤ N, M ≤ 500, 1 ≤ Q ≤ 10^5).
  • N dòng tiếp theo: Mỗi dòng gồm M số nguyên A[i][j].
  • Q dòng tiếp theo: Mỗi dòng gồm 4 số nguyên r1 c1 r2 c2.
Dữ liệu ra (Output)
  • Gồm Q dòng, mỗi dòng là tổng hình chữ nhật con tương ứng.
Ví dụ mẫu
Sample Input 1
3 3 2
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3
Sample Output 1
12
28
Draft saved