[11660] 구간 합 구하기5

사각형의 합을 미리 구해놔야 함

1. 원본 데이터 (Input)

(행\열)	1	2	3
1행	1	2	3
2행	4	5	6
3행	7	8	9

 

2. 누적 합 표 (DP 테이블) 계산 

dp[i][j] = dp[i-1][j] (위쪽 합) + dp[i][j-1] (왼쪽 합) - dp[i-1][j-1] (대각선 중복) + 원본[i][j]

[최종 완성된 DP 테이블]

(행\열)	1	2	3
1행	1	3	6
2행	5	12	21
3행	12	27	45

---

3. 구간 합 구하기 예시

[계산 공식] 결과 = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]

 

예시 ) (2, 2)부터 (3, 3)까지의 합을 구하라고 한다면

 

• 전체 면적: dp[3][3] = 45
• 위쪽 영역 빼기: dp[1][3] = 6 (1행 전체)
• 왼쪽 영역 빼기: dp[3][1] = 12 (1열 전체)
• 중복으로 빠진 대각선 더하기: dp[1][1] = 1

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().strip().split())
gra = [[0] * (N + 1)]
# 입력
for _ in range(N):
    li = list(map(int, input().strip().split()))
    gra.append([0] + li)

dp = [[0] * (N + 1) for _ in range(N + 1)]
# 구간합 구하기
for i in range(1, N + 1):
    for j in range(1, N + 1):
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + gra[i][j]

# 좌표 입력
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().strip().split())
    result = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]
    print(result)