[Algorithm] 백준 11660 : 구간합 구하기

 

* 구간합 사용 이유

Prefix Sum을 사용하면 배열의 특정 구간의 합을 O(1) 시간에 구할 수 있기 때문이다.

배열의 크기가 크고, 구간 합을 여러 번 계산해야 하는 경우에 유용하다.

=> 데이터 분석, 이미지 처리, 게임 개발, 금융 데이터 분석 등 대용량 데이터에서 특정 구간의 통계치를 빠르게 계산해야 하는 경우에 유용

 

"""
문제: 11660. 구간합 구하기

1. 아이디어
- M이 매우 크기 때문에 미리 합이 구해진 구간합 배열: prefix_arr
- D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]

2. 시간복잡도
O(N^2+M)

3. 자료구조
prefix_arr = int[N+1][N+1]

"""
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
q_arr = [list(map(int, input().split())) for _ in range(M)]

prefix_arr = [[0]*(N+1) for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, N+1):
        prefix_arr[i][j] = arr[i-1][j-1]+prefix_arr[i-1][j]+prefix_arr[i][j-1]-prefix_arr[i-1][j-1]

for x1,y1,x2,y2 in q_arr: #바로 구간합 배열에서 출력해줄 수 있다.
    result = prefix_arr[x2][y2]-prefix_arr[x1-1][y2]-prefix_arr[x2][y1-1]+prefix_arr[x1-1][y1-1]
    print(result)