---
title: "펜윅 트리: 최하위 비트로 누적 구간을 나누기"
author: "Lee"
published_at: "2026-10-18T13:38:01.696Z"
updated_at: "2026-09-30T09:51:42.528Z"
tags: ["컴퓨터공학","자료구조"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%ED%8E%9C%EC%9C%85-%ED%8A%B8%EB%A6%AC-%EC%B5%9C%ED%95%98%EC%9C%84-%EB%B9%84%ED%8A%B8%EB%A1%9C-%EB%88%84%EC%A0%81-%EA%B5%AC%EA%B0%84%EC%9D%84-%EB%82%98%EB%88%84%EA%B8%B0"
ai_assisted: false
---

# 펜윅 트리: 최하위 비트로 누적 구간을 나누기

[원문](https://ariser.io/@writer_a1cd615ab19e/%ED%8E%9C%EC%9C%85-%ED%8A%B8%EB%A6%AC-%EC%B5%9C%ED%95%98%EC%9C%84-%EB%B9%84%ED%8A%B8%EB%A1%9C-%EB%88%84%EC%A0%81-%EA%B5%AC%EA%B0%84%EC%9D%84-%EB%82%98%EB%88%84%EA%B8%B0)

펜윅 트리, 또는 이진 인덱스 트리는 누적합과 점 갱신을 O(log n)에 처리하는 간결한 자료구조다. 노드를 명시적으로 연결하지 않고 1부터 시작하는 배열 인덱스의 이진 표현으로 담당 구간을 정한다.

![접두사 1부터 6을 TREE6의 5부터 6과 TREE4의 1부터 4로 나누는 펜윅 트리](/api/v1/media/419fafc0-1041-4030-b2a4-4e369cfade3c)

*접두사 질의는 인덱스의 마지막 1비트를 제거하며 저장된 구간을 합친다.*

### lowbit가 담당 구간의 길이다

lowbit(i)=i&(-i)는 이진수 i의 가장 낮은 1비트만 남긴다. tree[i]에는 원본 배열의 i-lowbit(i)+1부터 i까지의 합을 저장한다. 예를 들어 12는 이진수 1100이므로 lowbit=4이고 9부터 12까지를 담당한다.

접두 합을 구할 때 i에서 lowbit(i)를 빼면 아직 더하지 않은 앞 구간의 끝으로 이동한다. 13의 경우 [13,13], [9,12], [1,8]을 합쳐 [1,13] 전체를 얻는다. 구간들이 겹치지 않는다는 점이 중요하다.

```python
class Fenwick:
    def __init__(self, length):
        self.length = length
        self.tree = [0] * (length + 1)

    def add(self, index, delta):
        while index <= self.length:
            self.tree[index] += delta
            index += index & -index

    def prefix_sum(self, index):
        result = 0
        while index > 0:
            result += self.tree[index]
            index -= index & -index
        return result

    def range_sum(self, first, last):
        return self.prefix_sum(last) - self.prefix_sum(first - 1)
```

위 코드의 갱신 인덱스는 1 이상이어야 한다. 0을 넣으면 lowbit가 0이라 반복문이 진행하지 않는다. 범위 질의는 양끝을 포함하며, 외부 배열이 0 기반이라면 변환 규칙을 API에서 명확히 정한다.

### 점 갱신은 반대 방향으로 이동한다

원소 i에 delta를 더하면 그 원소를 포함하는 더 큰 요약 구간들이 변한다. i+=lowbit(i)를 반복하여 필요한 칸만 갱신한다. 새 값으로 교체하려면 이전 값과의 차이를 계산해야 한다. add 연산을 대입 연산으로 오해하면 누적 결과가 틀어진다.

질의와 갱신마다 비트가 변해 단계 수가 O(log n), 공간은 O(n)이다. 모든 원소를 add로 넣으면 초기화 O(n log n)이지만 선형 구성 방법도 있다. 구현이 짧다는 사실과 모든 작업이 O(1)이라는 주장은 다르다.

구간 합은 두 접두 합의 차이로 얻으므로 빼기라는 역연산을 활용한다. 일반 최솟값처럼 역연산이 없는 집계에는 같은 방식으로 임의 구간을 처리할 수 없다. 제한된 갱신에서 특별한 변형이 가능해도 보편적인 합 구현과 구별해야 한다.

빈번한 수치 누적, 빈도 집계, 순위 관련 계산에 유용하다. 복잡한 구간 정보가 필요하면 세그먼트 트리가 더 유연할 수 있다. 펜윅 트리의 핵심은 각 칸의 구간 의미와 두 방향의 인덱스 이동을 동시에 이해하는 것이다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)