백준_11660_구간 합 구하기(누적합)

from sys import stdin
n, m = [int(v) for v in input().split()]

table = [[0]*(n) for _ in range(n)]
for i in range(n):
    table[i] = list(map(int, stdin.readline().split()))

sum_table = [[0]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, n+1):
        sum_table[i][j] = sum_table[i-1][j] + sum_table[i][j-1] + table[i-1][j-1] - sum_table[i-1][j-1]

for _ in range(m):
    start_x, start_y, end_x, end_y = list(map(int, stdin.readline().split()))
    print(sum_table[end_x][end_y] - sum_table[end_x][start_y-1] - sum_table[start_x-1][end_y] + sum_table[start_x-1][start_y-1] )

이런 2차원 리스트의 누적 합을 구할 때 생각해야 할 점은

초록색 부분의 누적 합을 구하기 위해서는 파란색 두 개를 더해 준 후 겹친 부분인 빨간 색 부분을 빼 줘야 하는 것이다.

반대로 나중에 초록색 좌표의 누적 합을 구할 때는 구하고자 하는 좌표에서 파란색 두개를 빼주고 빨간 색에 해당하는 누적 합을 구해줘야 한다.