Ma Trận Tổng Tiền Tố 2D

Buổi 15 — Prefix Sum & Difference Array Buổi 16 — Contest Chặng 2
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho ma trận $N \times M$ số nguyên. Trả lời $Q$ truy vấn, mỗi truy vấn cho $(r_1, c_1, r_2, c_2)$, tính tổng các phần tử trong hình chữ nhật con từ $(r_1, c_1)$ đến $(r_2, c_2)$.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $M$ $(1 \le N, M \le 1000)$.
  • $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên $(|a_{ij}| \le 10^6)$.
  • Dòng tiếp theo chứa số nguyên $Q$ $(1 \le Q \le 10^5)$.
  • $Q$ dòng tiếp theo, mỗi dòng chứa $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)$.
Dữ liệu ra
  • Với mỗi truy vấn, in ra tổng trên một dòng.
Ví dụ
Input Output
3 3
1 2 3
4 5 6
7 8 9
2
1 1 2 2
1 1 3 3
12
45
Giới hạn
  • $1 \le N, M \le 1000$
  • $|a_{ij}| \le 10^6$
  • $1 \le Q \le 10^5$
Draft saved