BOJ [11660]

import sys
sys.stdin.readline
sys.setrecursionlimit(10**6)

n,m=map(int,input().split())
sum=[[0 for _ in range(n+1)] for _ in range(n+1)]

arr=[list(map(int,sys.stdin.readline().split()))for _ in range(n)]

for x in range(1,n+1):
    for y in range(1,n+1):
        sum[x][y]=arr[x-1][y-1]+sum[x-1][y]+sum[x][y-1]-sum[x-1][y-1]
for _ in range(m):
    x1,y1,x2,y2=map(int,sys.stdin.readline().split())
    ans=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]
    print(ans)

범위~범위 탐색을 하게 되면 연산 횟수가 너무 많아지기 때문에
A B
C D 구역으로 나누어서 D-B-C+A(두번 빠졌기 때문에 한번 +)의 개념으로 문제를 풀었다.