[Algorithm] 누적 합(Prefix sum)

✨누적 합(Prefix sum)

주어진 배열에서 각 위치까지의 합을 미리 계산하여 배열에 저장해 놓는 알고리즘
빠른응답속도
추가 메모리 사용

 

 

 

ex)  백준 11659번 구간 합 구하기 4

https://www.acmicpc.net/problem/11659

import sys

N,M=map(int,sys.stdin.readline().rstrip().split(" "))
li=list(map(int,sys.stdin.readline().rstrip().split(" ")))

li2=[0]
sm=0
for i in li:
    sm+=i
    li2.append(sm)
    
for i in range(M):
    a,b=map(int,sys.stdin.readline().rstrip().split(" "))
    sys.stdout.write(str(li2[b]-li2[a-1])+"\n")

 

누적합 리스트를 미리 만들어주고 구간합을 미리 만든 누적합 리스트의 차이를 통해 해결했다.

 

 

 

 

 

 

 

 

 

 

🎈참고자료

https://ji-musclecode.tistory.com/38
https://velog.io/@vldzm4268/52-%EB%88%84%EC%A0%81%ED%95%A9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Cumulative-sum-algorithm