문제 설명

당신은 m x n 크기의 농장을 관리하고 있습니다. 각 칸에는 해당 구역의 수확량이 기록되어 있습니다. 여러 개의 쿼리가 주어지며, 각 쿼리는 직사각형 영역 (r1, c1)부터 (r2, c2)까지의 총 수확량을 묻습니다. 2D 누적합을 이용해 각 쿼리를 O(1)에 처리하세요.

입력

출력

제약 조건

• •1 <= m, n <= 1000
• •0 <= 각 수확량 <= 100
• •0 <= r1 <= r2 < m, 0 <= c1 <= c2 < n

예제

grid = [[1,2,3],[4,5,6],[7,8,9]], query = (0,0,1,1)

12

grid = [[1,2,3],[4,5,6],[7,8,9]], query = (1,1,2,2)

28