Sản Lượng Lúa Vùng Chữ Nhật Đồng Bằng Sông Cửu Long

Mô tả

Mùa lúa chín rải đều khắp Đồng bằng Sông Cửu Long, anh Ba phụ trách thống kê sản lượng cho một mạng lưới các trạm thu mua. Bản đồ vùng được chia thành lưới ô vuông kích thước H hàng × W cột, mỗi ô ghi sản lượng lúa tại trạm tương ứng (tính bằng tấn).

Đầu năm, anh nhận được một danh sách gồm Q truy vấn. Mỗi truy vấn yêu cầu tính tổng sản lượng lúa trong vùng hình chữ nhật có góc trên trái là ô (r1, c1) và góc dưới phải là ô (r2, c2), đánh số từ 0. Vì số truy vấn khá lớn, anh Ba cần một cách trả lời nhanh chứ không thể duyệt từng ô cho mỗi lần hỏi.

Nhiệm vụ của bạn là xây dựng bộ tiền tố tổng 2D rồi trả lời lần lượt từng truy vấn, trả về danh sách Q tổng theo thứ tự đầu vào.

Đầu vào

• grid: mảng 2 chiều số nguyên kích thước H × W.
• queries: mảng các truy vấn, mỗi truy vấn là một mảng 4 số nguyên [r1, c1, r2, c2].

Biết rằng 0 ≤ r1 ≤ r2 < H, 0 ≤ c1 ≤ c2 < W.

Đầu ra

• Trả về mảng số nguyên độ dài Q, phần tử thứ i là tổng sản lượng lúa của vùng chữ nhật tương ứng truy vấn thứ i.

Ràng buộc

• 1 ≤ H, W ≤ 1000
• 1 ≤ Q ≤ 10^5
• -10^6 ≤ grid[i][j] ≤ 10^6 (một số ô có thể ghi số âm do trạm báo hao)
• Tổng sản lượng mỗi truy vấn nằm trong khoảng [-10^9, 10^9].

Ví dụ

grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] queries = [[0, 0, 1, 1], [1, 1, 2, 2], [0, 0, 2, 2]]

Giải thích từng truy vấn:

1. Vùng [0,0] đến [1,1] gồm các ô 1, 2, 4, 5 → tổng = 12.
2. Vùng [1,1] đến [2,2] gồm các ô 5, 6, 8, 9 → tổng = 28.
3. Toàn bộ lưới 3×3 → tổng = 45.

Kết quả: [12, 28, 45].