기상 격자 구역 조회

문제

전국을 N행 M열 격자로 나눈 기상 관측망이 있습니다. grid[i][j]는 격자의 i+1행 j+1열 지점에서 측정한 평년 대비 온도 편차(정수, 음수 가능)입니다.

분석팀은 여러 개의 직사각형 구역에 대해 편차 총합을 요청합니다. 질의 queries[k] = [r, c, h, w]는 다음을 의미합니다.

• r, c: 구역 좌상단 칸의 행 번호와 열 번호 (1부터 시작)
• h, w: 구역의 높이와 너비 (칸 개수)

즉 이 구역은 r행부터 r+h-1행까지, c열부터 c+w-1열까지의 직사각형입니다.

각 질의 구역에 속한 편차의 총합을 질의가 주어진 순서대로 담은 배열을 반환하는 solution(grid, queries) 함수를 작성하세요.

예시

grid = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]
queries = [[1,1,2,2], [2,2,2,2], [1,1,3,3], [3,1,1,3]]
→ [12, 28, 45, 24]
 
  [1,1,2,2] : 1+2+4+5 = 12       (1~2행, 1~2열)
  [2,2,2,2] : 5+6+8+9 = 28       (2~3행, 2~3열)
  [1,1,3,3] : 격자 전체 = 45
  [3,1,1,3] : 7+8+9 = 24         (3행 한 줄)

grid = [
  [ 3, -2,  1],
  [-5,  4, -1],
  [ 2,  0, -3]
]
queries = [[1,2,2,2], [2,1,2,1], [1,1,1,1]]
→ [2, -3, 3]
 
  [1,2,2,2] : (-2)+1+4+(-1) = 2
  [2,1,2,1] : (-5)+2 = -3
  [1,1,1,1] : 3

제약 조건

• 1 ≤ N, M ≤ 300 (grid는 모든 행의 길이가 같은 직사각형 격자)
• -1000 ≤ grid[i][j] ≤ 1000
• 1 ≤ queries.length ≤ 50,000
• 모든 질의 구역은 격자 안에 완전히 들어갑니다. 즉 1 ≤ r, 1 ≤ c, 1 ≤ h, 1 ≤ w, r + h - 1 ≤ N, c + w - 1 ≤ M입니다.
• 같은 구역이 여러 번 질의될 수 있습니다.
• 반환 배열의 길이는 queries.length와 같아야 합니다.

시간 복잡도 목표: O(N×M + Q) 질의마다 구역을 직접 순회하면 O(Q×N×M)이 되어 최악의 경우 45억 번 가까이 더해야 합니다. 질의 수와 무관하게 격자를 한 번만 훑는 방법으로 풀어야 합니다.