배열의 특정 구간에 대한 sum을 반복적으로 계산해야할 때 사용
📍구분
| 값을 변경하지 않는 경우 (immutable) |
값을 변경하는 경우 (mutable) |
|
| 1차원 | prefix sum | binary indexed tree (Fenwick tree) segment tree sqrt-decomposition |
| 2차원 | summed-area table (integral image) |
binary indexed tree (Fenwick tree) segment tree sqrt-decomposition |
📍예시 (sum)
A : array
S : sum (계산의 편의상 0부터 시작)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A 1 3 11 6 7 10 14 9 18 16 5 4 2 8 19
S 0 1 4 15 21 28 38 52 61 79 95 100 104 106 114 133
🤔A[5] + A[6] + A[7] + A[8] + A[9] 을 쉽게 구하는 방법?
✅9까지의 합 에서 4까지의 합을 뺀다
즉, S[10] - S[5] = 95 - 28 = 67
📍prefix sum
S[i + 1] = S[i] + A[i], 0 <= i < n
📍range sum
A[L] + A[L + 1] + A[L + 2] + ... + A[R - 1] + A[R]
= S[R + 1] - S[L]
📍곱하기, XOR 연산에 대해서도 작동
곱하기 예시
prefix product
S[i + 1] = S[i] + A[i], 0 <= i < n
range product
A[L] + A[L + 1] + A[L + 2] + ... + A[R - 1] + A[R]
= S[R + 1] / S[L]