[파이썬] 구간 합 빠르게 구하기 : 누적 합을 이용해서

구간 합 

N개의 수에 대해서 M개의 구간 정보로 구간 합을 구해야 하는 경우

• 구간 합을 완전 탐색을 통해서 구할 경우 O(NM)의 시간 복잡도
• 결국 N, M이 클 경우 별도의 방법 필요

누적합(Prefix sum)

• N개의 수는 변하지 않고 그대로이며 M개의 구간 정보만 바뀌는 상황일 때, N개의 수에 대한 누적합을 계산하여 별도의 리스트에 미리 저장해줌
  • 필요한 시간 복잡도 O(N)
• 이 경우 M개의 구간 정보 L, R에서 구간 합을 구할 경우 P[R] - P[L-1]을 통해서 빠르게 구할 수 있음
  • 인덱싱만 하면 되기 때문에 각 구간 정보당 O(1)의 시간 복잡도를 가지게 됨
• 따라서 구간 합을 구할 때 누적합을 이용하게 되면 O(N + M)의 시간 복잡도만으로 가능하다.

 

N개의 데이터

prefix sum을 계산

---

참고

이것이 취업을 위한 코딩 테스트다 with 파이썬