정의

누적합(Prefix Sum)은 배열의 첫 번째 원소부터 현재 원소까지의 합을 미리 계산해두어, 임의의 구간 합을 O(1)에 구할 수 있게 하는 기법입니다.

핵심 특성

• ✓prefix[i] = arr[0] + arr[1] + ... + arr[i-1]
• ✓구간 합: sum(l, r) = prefix[r+1] - prefix[l]
• ✓O(n) 전처리 후 무한 쿼리 O(1)
• ✓2D로 확장하면 부분 행렬 합도 O(1)

시간 복잡도