🫂 Prefix Sum

1D Prefix Sum

✊🏻 구간 합 문제는 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 계산하는 문제 유형을 뜻한다.

 

✊🏻 예를 들면, 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정했을 때, 2번째 수부터 4번째 수까지의 합은 20 + 30 + 40인 90이 된다.

 

✊🏻 N개의 정수로 구성된 수열이 있고, M개의 query 정보가 주어진다. 각 query는 left와 right로 구성. 각 query에 대하여 [left, right] 구간에 포함된 데이터들의 합을 출력해야 한다. (수행 시간 제한은 O(N+M))

 

→ 위 예와 접목하자면, 5개의 데이터 (N=5)로 구성된 수열에서 매번 새로운 query 구간마다 해당 합을 구한다면 시간 복잡도는 O(N*M)

→ 이 때, 시간의 효율성을 위해 구간 합(Prefix Sum; Interval Sum) 아이디어를 사용!

 

※ 구간 합 = 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것 ※

→ 따라서 N개의 수 위치 각각에 대하여 접두사 합을 계산하여 P에 저장한 뒤, 매 M개의 쿼리 정보를 확인할 때 구간 합은 P[Right] - P[Left-1]

✊🏻 앞에 0을 붙이면 i번째부터 j번째의 부분합을 구할 때, i = 1일 때의 처리를 별도로 하지 않아도 된다. 위 그림에서 pre_sum = [0, 10, 30, 60, 100, 150]으로 만들었다면 1번째부터 3번째의 부분합은 위 구간합 공식에 의해 pre_sum[3] - pre_sum[0]으로 쉽게 구할 수 있다. 만약 앞에 0을 붙이지 않았다면 i가 1일 때 별도로 식을 추가로 만들어주어야 한다.

2D Prefix Sum

✊🏻1차원과 다르게 2차원 배열에서의 부분합은 포함-배제의 원리를 사용해 누적합을 구한다. 아래 그림을 참고하자.

: 위 노란색 부분 사각형(3x3) 내의 9개의 숫자의 합(부분합)을 구하고자 한다. 일단 전체 파란색 사각형 (1)에 들어간 모든 숫자의 합에서 (2) 빨간색 사각형 내의 모든 숫자의 합을 빼고, 초록색 사각형 (3)에 들어간 모든 숫자의 합도 뺀다. 그 다음, (2)와 (3)을 공통으로 뺐으므로, 두 번 뺀 주황색 사각형 (4)를 한 번 더한다. (포함 - 배제의 원리)

 

✊🏻① 주어진 2차원 배열에서 누적합 구하기

: 이미 주어진 2차원 배열에서 2차원 누적합 배열을 구할 수도 있고, 각 row를 입력 받는 과정에서 굳이 숫자로만 주어진 2차원 배열을 만들 필요 없이 도중도중 2차원 누적합 배열을 만들 수도 있다. 

 

★ 이 때, 1차원 누적합 배열과 동일하게 2차원 누적합 배열 위쪽 / 왼쪽에 0을 일렬로 만드는게 편하다. 이후 공식 한 번만 써서 한번에 2차원 부분합을 구할 수 있다!

2D Cumsum(Prefix Sum) Array & 2D Sum of Sub-Matrix

 ex) NxM size의 2D array를 만든다 가정. 그러면 2차원 누적합 배열(psum) size는 (N+1)x(M+1)이 되고, 아래 예시로는 N=5, M=4

 

① N과 M을 입력 받고, psum의 첫번째 행은 (M+1)개의 0으로 구성된 list로 일단 생성

N,M=map(int,input().split())
psum=[[0]*(M+1)]

 

② 1부터 N행까지 for문으로 돌린다. 먼저 psum에 append할 list를 [0]으로 초기화한다. 

for i in range(1,N+1):
    psum.append([0])

 

③ 입력 받은 한 행(row)의 앞 부분에 0을 붙인 list l 생성

for i in range(1,N+1):
    psum.append([0])
    l=[0]+list(map(int,input().split()))

 

④ list l의 두번째 원소(0 그 다음)부터 for문을 돌려 (0,0)부터(2D array의 왼쪽 끝 시작부분) 현재 원소를 포함한 2차원 배열까지의 누적합을 psum[-1]에 업데이트한다.

: 위 그림을 예로 들자면 그림 왼쪽 직사각형에서 2x2 형태의 하늘색 사각형 부분합을 구하고자 한다. 6을 넣으려고 할 때 (본인 6) + (왼쪽 빨간색 직사각형의 누적합인 5) + (위 연두색 직사각형의 누적합인 8) - (두 직사각형의 공통 부분 보라색 누적합 3)으로 6 + 5 + 8 - 3이 되어 16이 된다. 이는 아래와 같이 파이썬 코드로 구현 가능

for i in range(1,N+1):
    psum.append([0])
    l=[0]+list(map(int,input().split()))
    for x in range(1,len(l)):
        psum[-1].append(l[x]+psum[i][x-1]+psum[i-1][x]-psum[i-1][x-1])

 

⑤ 이제 2D cumulative sum array(누적합 2차원 배열)를 만들었으므로 자유롭게 2D Sum of Sub-Matrix(부분합 2차원 배열)을 구해보자.

 

ex) 완성된 2D cumulative sum array를 활용, (2,2)부터 (3,4)까지의 부분합 구하기(x와 y 모두 붙인 0 제외한 내용의 왼쪽 위부터 1부터 시작한다 가정)

: 위 하늘색 사각형의 부분합을 구하는 것이므로 (3,4)까지의 부분합인 연두색 사각형 누적합(55) - (3,1)까지의 부분합인 노란색 사각형 누적합(13) - (1,4)까지의 부분합인 주황색 사각형 누적합(17) + 공통 부분 누적합 (3) 결과 (55 - 13 - 17 + 3) 28이 나온다. 28은 곧 6 + 4 + 10 + 4 + 3 + 1 결과와 같음을 알 수 있다.

 

: 즉 code로 나타내기 위해 index를 정해본다면 (x1,y1)번째부터 (x2,y2)번째 까지의 부분합을 구하기 위해서는 공식 psum[x2][y2] - psum[x2][y1-1] - psum[x1-1][y2] + psum[x1-1][y1-1]로 구할 수 있다.

for _ in range(int(input())):
    x1,y1,x2,y2=map(int,input().split())
    print(psum[x2][y2]-psum[x2][y1-1]-psum[x1-1][y2]+psum[x1-1][y1-1])

code

(1) 1D Prefix Sum

#1D Prefix Sum
n=5
data=[10,20,30,40,50]

sum_value=0
prefix_sum=[0]

for i in data:
    sum_value+=i
    prefix_sum.append(sum_value)

left=3
right=4
print(prefix_sum[right] - prefix_sum[left-1]) #70

(2) 2D Prefix Sum

: NxM 형태의 2D array를 row별로 입력 받고, 입력 받으면서 바로 prefix sum 2D Array를 만든 뒤, (x1,y1) ~ (x2,y2)번째 사이의 모든 원소 2D 부분 누적합 출력 (BOJ 2167 내용)

N,M=map(int,input().split())
psum=[[0]*(M+1)]
for i in range(1,N+1):
    psum.append([0])
    l=[0]+list(map(int,input().split()))
    for x in range(1,len(l)):
        psum[-1].append(l[x]+psum[i][x-1]+psum[i-1][x]-psum[i-1][x-1])

for _ in range(int(input())):
    x1,y1,x2,y2=map(int,input().split())
    print(psum[x2][y2]-psum[x2][y1-1]-psum[x1-1][y2]+psum[x1-1][y1-1])

Exercises

★ <BOJ S5 2167 2차원 배열의 합> ★

: 2차원 배열 누적합 대표 문제

 

★ <BOJ S1 11660 구간 합 구하기 5> ★

: 2167과 동일. 다만 NxN 2차원 배열에서 누적합 구하기. size의 제한이 커 위 2167과 다르게 누적합 알고리즘으로만 풀이 가능

 

★ <BOJ S3 11659 구간 합 구하기 4> ★

: 1차원 배열 누적합 대표 문제

 

★ <BOJ S4 13900 순서쌍의 곱의 합> ★

: 서로 다른 두 위치의 두 수를 정할 때 왼쪽부터 누적합 개념으로 mulsum 곱의 합 아이디어임을 알아차리는 것이 중요

---

1D prefix sum array 그림 이코테 2021 참고