누적합 알고리즘

[psychehose]

누적합 알고리즘

누적합(prefix sum) 알고리즘은 배열의 부분합을 빠르게 계산하는 데 사용되는 기법

1. 주어진 배열의 각 위치까지의 원소들의 합을 미리 계산해 놓는 방식
2. 원본 배열: A[1], A[2], ..., A[n]
3. 누적합 배열: S[i] = A[1] + A[2] + ... + A[i]
4. 시간 복잡도
   • 전처리: O(n)
   • 구간 합 쿼리: O(1)
5. 특정 구간 [L, R]의 합을 S[R] - S[L-1]로 O(1) 시간에 계산 가능

관련문제: https://leetcode.com/problems/product-of-array-except-self/