누적합 구하기 (Prefix Sum)

N개의 인덱스를 가지는 배열 arr가 있을 때, 배열의 i~j 인덱스의 합을 구하려고 한다.

 

 

딱 한개의 구간합을 구하는 문제가 주어진다면 단순히 반복문에서 arr[i]~arr[j]까지의 합을 더해나가면 되겠지만, 주어진 배열에서 여러 구간합을 구해야한다면, 반복되는 작업을 피하기 위해 누적합을 저장하는 배열을 하나 만들어 놓는 것이 좋다.

 

(i <= j 일 때) arr[i]~arr[j]까지의 합 = arr[0]~arr[j]까지의 합 - arr[0]~arr[i-1]까지의 합 이다.

즉, p[i] = arr[0]~arr[j]까지의 합 이라고 한다면, arr[i]~arr[j]까지의 합 = p[j] - p[i-1] 이다.

 

구간합 계산을 위해 쓰이는 것이 바로 누적합(Prefix Sum) 인데,

이는 p[n] = p[n-1] + arr[n] 임을 이용하여 p배열을 만드는 방식이다.

p = [0 for _ in range(N)]
p[0] = 0

for n in range(1,N):
    p[n] = p[n-1] + num[n]

 

[연습문제1_기초] 2021.07.25 - [Algorithm/문제풀이] - [Python][백준] 11659_구간 합 구하기 4

[연습문제2_응용] 2021.07.29 - [Algorithm/문제풀이] - [Python][백준] 3020_개똥벌레

 

 

 

[참고] https://namnamseo.tistory.com/entry/%EC%B5%9C%EB%8C%80%EC%9D%98-%EB%B6%80%EB%B6%84%ED%95%A9-%EC%B0%BE%EA%B8%B0

Prefix sum