구간마다 합을 계산하지 않고 미리 저장하여 꺼내 씀으로써 시간복잡도 감소

합 배열 S : S[i] = S[i-1]+A[ i]

j ~ i구간 합 : sumList[j] - sumList[i-1]

일차원 배열의 구간 합

# num : 데이터 리스트 / sumList : 합 배열 -> 인덱스 서로 맞추기 위해 0 미리 넣음
num = []
sumList = [0]

Sum = 0
for a in range(N):
    Sum+=num[a]
    sumList.append(Sum)

# prefix_sum : 구간 합(i~j까지)
prefix_sum = sumList[j] - sumList[i-1]

이차원 배열의 구간 합

# A : 데이터 리스트 -> 인덱스 서로 맞추기 위해 0 미리 넣음
A = [[0] * (n+1)]

for i in range(n):
    A_row = [0]+[int(x) for x in input().split()]
    A.append(A_row)

# D : 합 배열 -> 인덱스 서로 맞추기 위해 0 미리 넣음
D = [[0] * (n+1) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,n+1):
        D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

# result : 구간 합 - (x1,y1) ~ (x2,y2)
result = D[x2][y2] - D[x1-1][y2] -D[x2][y1-1]+D[x1-1][y1-1]