import sys
input = sys.stdin.readline

N, M = map(int, input().split())
dp = [[0] * (N+1)]

for _ in range(N):
    nums = [0] + list(map(int, input().split()))
    dp.append(nums)

for i in range(1, N+1):
    for j in range(1, N):
        dp[i][j+1] += dp[i][j]
    
for j in range(1, N+1):
    for i in range (1, N):
        dp[i+1][j] += dp[i][j]

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

 

이 문제를 관통하는 핵심아이디어는 아래와 같이, 입력 받은 표의 수를 행축으로 합을 구해준 다음 열 축으로 합을 구해주는 것이다. 

 

행 슬라이딩 합 이후 열 슬라이딩 합까지 해준 테이블을 우리는 DP 테이블이라 하자. 이후 구간합을 구하기 위한 예시로 (1, 1)과 (4, 4)를 입력 받았다면 구간합은 입력 받은 표의 빨간 영역의 합이 될 것이다. (45 = 3+4+5+4+5+6+5+6+7)

빨간 영역의 합을 구하기 위해선 전체 입력 받은 표에서 파란 부분을 각각 빼주고 초록 부분이 두 번 차감되었으니 한 번 더해주는 것이다. 

 

전체 입력 받은 표를 대표하는 값은 (1, 1) ~ (4, 4)의 합이 모두 저장된 DP[$x_2$][$y_2$]에 있다. 또한

첫 번째 파란색 영역을 대표하는 값은 DP[$x_1-1$][$y_2$]에 저장돼 있으며

두 번째 파란색 영역을 대표하는 값은 DP[$x_2$][$y_1-1$]에 저장돼 있으며

세 번째인 초록 영역을 대표하는 값은 DP[$x_1-1$][$y_1-1$]에 저장돼 있다.

 

따라서 최종 점화식은 dp[$x2$][$y2$] $-$ dp[$x_1-1$][$y_2$] $-$ dp[$x_2$][$y_1-1$] $+$ dp[$x_1-1$][$y_1-1$]이 된다.

+ Recent posts