[11660] 구간합 구하기5 (2차원 합배열)

11660번: 구간 합 구하기 5

 

분석

2차원 합배열 채우기 : d[i][j] = d[i-1][j] + d[i][j-1] - d[i-1][j-1] + a[i][j]

2차원 구간합 구하기 : d[x2][y2]-d[x1-1][y2]-d[x2][y1-1]+d[x1-1][y1-1]

 

풀이

import sys
input=sys.stdin.readline

n,m = map(int, input().split())

# 리스트
a=[[0]*(n+1)]
# 합배열
d=[[0]*(n+1) for _ in range(n+1)]

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

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

# 질의
for _ in range(m):
    x1,y1,x2,y2=map(int, input().split())
    res=d[x2][y2]-d[x1-1][y2]-d[x2][y1-1]+d[x1-1][y1-1]
    print(res)​