Elearning CodePath – CTP Online Judge

Truy vấn tổng hình chữ nhật

A2D_RECT_SUM

🟢 Easy

## Đề bài

Cho một ma trận gồm `n` hàng và `m` cột.

Có `q` truy vấn. Mỗi truy vấn gồm bốn số `x1, y1, x2, y2`, yêu cầu tính tổng các phần tử nằm trong hình chữ nhật:

- góc trên trái là ô `(x1, y1)`;
- góc dưới phải là ô `(x2, y2)`.

Bảo đảm `1 <= x1 <= x2 <= n` và `1 <= y1 <= y2 <= m`.

## Dữ liệu vào

- Dòng 1 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 mô tả ma trận.
- `q` dòng tiếp theo, mỗi dòng chứa bốn số nguyên `x1 y1 x2 y2`.

## Dữ liệu ra

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

## Ràng buộc

- `1 <= n, m <= 700`
- `n * m <= 200000`
- `1 <= q <= 200000`
- `-10^9 <= a[i][j] <= 10^9`
- `1 <= x1 <= x2 <= n`
- `1 <= y1 <= y2 <= m`

## Subtask

| Subtask | Điểm | Ràng buộc thêm |
|---|---:|---|
| 1 | 30 | `n, m, q <= 10` |
| 2 | 35 | `n, m <= 50`, `q <= 1000`, `0 <= a[i][j] <= 10^6` |
| 3 | 35 | Không có ràng buộc thêm |

## Ví dụ

### Input
```text
3 4 3
1 2 3 4
5 6 7 8
9 10 11 12
1 1 1 4
2 2 3 3
1 1 3 4
```

### Output
```text
10
34
78
```

## Giải thích ví dụ

- Hình chữ nhật `1 1 1 4` là hàng đầu tiên, tổng bằng `10`.
- Hình chữ nhật `2 2 3 3` gồm `6, 7, 10, 11`, tổng bằng `34`.
- Hình chữ nhật `1 1 3 4` là toàn bộ ma trận, tổng bằng `78`.

✅ Đã AC: 5 / 16 submissions