Prefix Sum(구간합), 누적합

어떠한 행렬이 주어지고, 그의 부분행렬의 합이 최대 혹은 최소가 되는 값을 찾을 경우에는 누적합과 Prefix Sum(구간합)을 사용한다.

 

1. 누적합

누적합은 0부터 해당 인덱스까지의 행렬의 값들을 모두 더하는 것이다. 만약 2차원 행렬에서 (i, j) 위치의 누적합 값은 (0, 0) ~ (i, j) 인덱스의 행렬의 값을 모두 더한 것이다.

예를 들면 아래와 같다.

인덱스	0	1	2	3	4	5
행렬 값	3	2	5	2	1	2
누적합	3	5	10	12	13	15

2차원 행렬의 경우 만약 행렬이 아래와 같을 때,

sum_arr[0][1] = arr[0][0] + arr[0][1],

sum_arr[1][1] = arr[0][0] + arr[0][1] + arr[1][0] + arr[1][1] 과 같다.

2	1	0	1
3	4	5	2
0	3	1	6
2	5	7	1

따라서 2차원 행렬의 누적합 행렬은 아래와 같다.

0	0	0	0	0
0	2	3	3	4
0	5	10	15	18
0	5	13	19	26
0	7	23	31	41

 

누적합 구하는 코드는 외우는 게 가장 편한데, 분석해보면 DP의 형태를 띈다.

이때, 특이한 점이 있다면 누적합을 넣을 행렬의 위와 왼쪽에 0으로 구성된 행 또는 열을 추가한다는 것이다.

 

따라서 N개 행과 M개의 열이 있는 행렬의 경우에 누적합을 구할 때는, 0~N-1 또는 0~M-1이 아니라 1~N, 1~M까지를 구해야 한다.

sum_arr[i][j] = arr[i-1][j-1] + sum_arr[i-1][j] + sum_arr[i][j-1] - sum_arr[i-1][j-1]

N, M = map(int, stdin.readline().split())    # N: 세로, M: 가로
# arr = list([[0] * (M+1)] + list([0] + list(map(int, input().split())) for _ in range(N)))   # 입력 행렬
arr = [list(map(int, input().split())) for _ in range(N)]

# 누적합 구하기
sum_arr = [[0] * (M+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, M+1):
        sum_arr[i][j] = arr[i-1][j-1] + sum_arr[i-1][j] + sum_arr[i][j-1] - sum_arr[i-1][j-1]

 

2. 구간합 (Prefix Sum)

• 구간합(Prefix Sum): 특정 구간의 합, 1차원 배열에서는 i ~ k 인덱스 사이의 값
• 부분합(Partial Sum): 처음부터 특정 인덱스까지의 합, 0 ~ k 인덱스 사이의 값들의 합
• 참고: https://hroad.tistory.com/52

[알고리즘] 구간 합 (Prefix Sum)

 

(i1, j1) ~ (i2, j2) 직사각형 행렬의 구간합 공식은 아래와 같다.

value = sum_arr[i2][j2] - sum_arr[i1-1][j2] - sum_arr[i2][j1-1] + sum_arr[i1-1][j1-1]