이 노트의 기준은 tree[i]가 원본의 특정 끝 구간을 책임지고, 인덱스의 최하위 1비트가 그 구간의 길이와 다음 이동을 함께 결정한다는 점입니다. 이 불변식을 기준으로 조회는 겹치지 않는 구간을 모으고 갱신은 해당 원소를 포함하는 상위 구간을 올려 가는 과정으로 읽으면 됩니다.
누적 합 조회와 이후 누적 합 갱신 비용
날짜별 판매량 배열에서 반복해서 구간 합을 조회한다고 합시다. 누적 합 prefix[i]를 저장하면 [l,r]의 합은 prefix[r]-prefix[l-1]로 즉시 구할 수 있습니다. 하지만 3일의 값이 바뀌면 3일 이후 누적 합을 모두 고쳐야 합니다.
값 수정이 자주 일어난다면 전체 누적 합 대신 일부 구간 합만 저장할 수 있습니다. Fenwick tree는 점 하나의 증가와 앞부분 합 조회를 모두 로그 시간에 처리하는 구조입니다. 여기서는 1-based 배열, 정수 합, 점 갱신에 집중합니다. 구간 전체 갱신이나 임의 집계 함수까지 같은 코드로 처리하지 않습니다.
lowbit와 각 칸의 담당 구간
lowbit(i) = i & -i는 양수 인덱스의 가장 낮은 1비트 값입니다. tree[i]에는 [i-lowbit(i)+1, i]의 합을 저장합니다. 예제 배열은 a=[2,1,3,4,2,5,1,6]입니다.
| i | 이진 표현 | lowbit | 저장 구간 | tree[i] |
|---|---|---|---|---|
| 1 | 0001 | 1 | [1,1] | 2 |
| 2 | 0010 | 2 | [1,2] | 3 |
| 3 | 0011 | 1 | [3,3] | 3 |
| 4 | 0100 | 4 | [1,4] | 10 |
| 5 | 0101 | 1 | [5,5] | 2 |
| 6 | 0110 | 2 | [5,6] | 7 |
| 7 | 0111 | 1 | [7,7] | 1 |
| 8 | 1000 | 8 | [1,8] | 24 |
포인터 트리를 따라가는 대신 인덱스의 이진 표현만으로 조회 방향과 갱신 방향을 계산합니다. 예를 들어 6(0110)의 lowbit는 2라서 tree[6]이 [5,6]을 맡고, prefix(7)에서는 7→6→4처럼 왼쪽 덩어리를 차례로 떼어 냅니다. 반대로 갱신은 3→4→8처럼 현재 위치를 포함하는 더 큰 구간으로 올라갑니다. 인덱스 0은 lowbit가 0이어서 이 루프가 전진하지 않으므로 1-based 계약을 코드와 호출부에서 함께 지켜야 합니다.
prefix(7)의 겹치지 않는 세 구간
그림을 글로 읽기
- tree[7] = 1: [7,7] 합 · 7 - lowbit(7) = 6
- tree[6] = 7: [5,6] 합 · 6 - lowbit(6) = 4
- tree[4] = 10: [1,4] 합 · 4 - lowbit(4) = 0
- 합계 18: 1 + 7 + 10
- tree[7] = 1 → tree[6] = 7: 왼쪽 남은 구간
- tree[6] = 7 → tree[4] = 10: 왼쪽 남은 구간
- tree[4] = 10 → 합계 18: 0에서 종료
조회 때는 이미 합산한 구간의 왼쪽으로 이동하므로 중복 합산하지 않습니다. 매번 최하위 1비트 하나를 지워 인덱스의 1비트 수만큼 이동합니다. 최대 로그 횟수에 끝나는 이유입니다.
점 갱신과 원소 포함 구간의 상향 경로
3번 값 3을 8로 바꾸려면 증가량은 8-3=5입니다. add(3,5)는 3, 4, 8번 노드를 갱신합니다.
| 방문 인덱스 | 포함 구간 | 변경 전 → 후 | 다음 인덱스 |
|---|---|---|---|
| 3 | [3,3] | 3 → 8 | 3+1=4 |
| 4 | [1,4] | 10 → 15 | 4+4=8 |
| 8 | [1,8] | 24 → 29 | 8+8=16, 종료 |
6번 노드는 [5,6]만 저장하므로 바꾸지 않습니다. 수정 후 prefix(7)=1+7+15=23입니다. 8을 그대로 더하면 새 값은 11이 되어 잘못되므로 증가와 대입의 인터페이스를 구분해야 합니다.
원리를 구현하는 슈도코드
add(index, delta):
require 1 <= index <= n
i = index
while i <= n:
tree[i] += delta
i += lowbit(i)
prefix(index):
require 0 <= index <= n
total = 0
i = index
while i > 0:
total += tree[i]
i -= lowbit(i)
return total
rangeSum(left, right):
require 1 <= left <= right <= n
return prefix(right) - prefix(left - 1)
setValue(index, newValue):
delta = newValue - values[index]
add(index, delta)
values[index] = newValue
처음에는 tree를 0으로 두고 각 값을 add하면 O(n log n)에 구성할 수 있습니다. 더 빠른 선형 구성도 있지만 위 불변식을 익힐 때는 단순 구성이 검산하기 쉽습니다. 입력 배열과 tree를 함께 유지하면 대입의 delta를 구하기 쉽고 메모리는 O(n)입니다.
이 슈도코드는 합·차이·인덱스 연산이 표현 가능한 범위에 있다고 가정합니다. 고정 폭 정수 구현에서 중간 합이 넘치는 경우도 확인해야 합니다. 여러 노드 중 일부만 갱신한 뒤 오류를 반환하면 구조가 깨지므로, 허용 범위를 사전 제한하거나 충분히 큰 타입·원자 변경 규칙을 사용합니다.
Fenwick tree 연산 범위와 적용 조건
| 요구 | 단순 누적 합 | Fenwick tree |
|---|---|---|
| prefix·구간 합 | O(1) 조회 | O(log n) 조회 |
| 점 값 변경 | 뒤 구간 O(n) 갱신 | O(log n) 갱신 |
| 저장 공간 | O(n) | O(n) |
| 거의 수정하지 않는 데이터 | 단순하고 유리 | 추가 복잡도가 불필요할 수 있음 |
구간 합은 덧셈의 역연산인 뺄셈으로 앞부분을 제거합니다. 최솟값에는 같은 역연산이 없으므로 minPrefix(r)-minPrefix(l-1) 같은 식은 의미가 없습니다. 범위 갱신·최솟값·복잡한 태그 합성은 해당 자료구조의 별도 조건을 확인해야 합니다.
음수 원소도 합과 점 갱신 자체에는 사용할 수 있습니다. 하지만 누적 합을 이진 탐색해 가중 추첨 위치를 찾으려면 가중치가 비음수여야 누적값이 단조입니다. “Fenwick을 썼다”는 이유로 음수 가중치 탐색까지 정당해지지는 않습니다.
기준 배열과 모든 구간의 합 대조
조회 구현을 검산할 때는 먼저 a=[2,1,3,4,2,5,1,6]에서 prefix(7)=18을 손으로 계산하고, 3번을 8로 바꾼 뒤 prefix(7)=23이 되는지 확인합니다. 그 다음 add(3,8)처럼 대입값을 delta로 착각한 경우에는 원본 대조에서 차이가 누적되는 것을 관찰하면 인터페이스 오류를 빠르게 분리할 수 있습니다.
예제의 모든 [l,r]에 대해 직접 더한 값과 rangeSum을 비교합니다. 이어서 첫·마지막 원소, 음수 delta, 같은 값 재설정, 반복 갱신을 넣고 매번 대조합니다. prefix(0)=0, 잘못된 add(0,...) 거절도 확인합니다.
큰 입력에서 로그 시간을 측정하기 전에 작은 입력의 저장 구간 불변식을 검사하세요. tree[i]가 항상 원본의 [i-lowbit(i)+1,i] 합인지 확인하면, 합계 하나만 맞는 우연과 올바른 갱신을 구분할 수 있습니다.