Truy vấn tổng ma trận con 2D

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

Cho ma trận số nguyên kích thước $N \times M$ (các hàng đánh số từ $1$ đến $N$, các cột từ $1$ đến $M$) và $Q$ truy vấn. Mỗi truy vấn gồm 4 số nguyên $r_1, c_1, r_2, c_2$ ($1 \le r_1 \le r_2 \le N$, $1 \le c_1 \le c_2 \le M$), yêu cầu tính tổng các phần tử trong hình chữ nhật con có góc trên trái $(r_1, c_1)$ và góc dưới phải $(r_2, c_2)$.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $N, M, Q$. $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên. $Q$ dòng cuối cùng, mỗi dòng chứa 4 số nguyên $r_1, c_1, r_2, c_2$.

Dữ liệu ra

Với mỗi truy vấn, in ra tổng hình chữ nhật con tương ứng trên một dòng.

Ví dụ
Input Output
3 4 2
1 2 3 4
5 6 7 8
9 10 11 12
1 1 2 2
2 2 3 4
14
54
2 2 2
-1 2
3 -4
1 1 2 2
1 2 2 2
0
-2
Giới hạn

$1 \le N, M \le 1000$, $1 \le Q \le 10^5$, $|A_{i,j}| \le 10^9$.

Draft saved