· 개발

펜윅 트리로 구간 합 구하기: i & -i가 고르는 구간과 O(log n)의 근거

펜윅 트리에서 i & -i가 각 칸의 구간을 정하는 방식을 원소 8개 예로 갱신·누적 합 루프와 함께 따라가고, 인덱스 규칙·구축 비용·오버플로·세그먼트 트리와의 차이를 정리했습니다.

개발알고리즘자료구조

배열 a의 원소를 수시로 바꾸면서 a[l] + … + a[r-1]도 자주 물어야 하는 경우가 있습니다. 누적 합 배열을 미리 만들어 두면 질의는 O(1)이지만, 원소 하나를 바꿀 때마다 그 뒤의 누적 합을 전부 고쳐야 해서 갱신이 O(n)입니다. 반대로 배열만 들고 있으면 갱신은 O(1), 질의는 O(n)입니다.

펜윅 트리(Fenwick tree, binary indexed tree)는 두 연산을 모두 O(log n)으로 맞춥니다. 저장 공간은 길이 n인 배열 하나입니다. 이 글에서는 AtCoder Library(ACL)의 fenwick_tree 문서와 구현을 기준으로, 각 칸이 어느 구간의 합을 들고 있는지, 두 루프가 왜 그 칸들만 방문하는지를 작은 예로 따라갑니다.

출발점: 누적 빈도표

이름의 출처는 Peter M. Fenwick이 1994년 Software: Practice and Experience 24권 3호(327–336쪽)에 낸 논문 “A new data structure for cumulative frequency tables”입니다. Crossref에 등록된 출판사 초록에 따르면, 이 논문은 동적 산술 부호화(arithmetic coding)에서 쓰는 누적 빈도를 관리하는 “binary indexed tree”를 제시합니다. 누적 빈도를 원소 번호의 이진 표현과 나란한 조각으로 나누고, 탐색도 번호의 이진 부호를 따라 진행한다는 설명이 초록에 있습니다.

다만 이 글을 쓰면서 확인한 것은 Crossref의 서지 정보와 초록까지입니다. Wiley의 논문 본문은 열리지 않았고, OpenAlex에도 공개 전문은 등록되어 있지 않았습니다. 아래 동작 설명은 ACL 문서와 소스 코드를 기준으로 했고, 원 논문의 증명이나 표기를 옮긴 것이 아닙니다.

ACL의 공개 API

ACL 문서가 정한 인터페이스는 다음과 같습니다.

호출 의미 조건 계산량
fenwick_tree<T> fw(n) 0으로 초기화된 원소 n개 O(n)
fw.add(p, x) a[p] += x 0 ≤ p < n O(log n)
fw.sum(l, r) a[l] + … + a[r-1] 0 ≤ l ≤ r ≤ n O(log n)

공개 인덱스는 0-based이고 구간은 반열린 구간 [l, r)입니다. 그런데 내부 루프는 1-based 번호로 돕니다. 이 두 규칙을 섞으면 대부분의 버그가 생기므로, 이 글에서는 공개 위치를 p, 내부 번호를 i(= p + 1)로 구분해 씁니다.

ACL 소스와 같은 구조로 다시 쓰면 이렇습니다. ACL은 값 타입을 템플릿 T로 받는데, 여기서는 읽기 쉽게 long long으로 고정했습니다.

struct Fenwick {
    int n;
    std::vector<long long> data;  // data[i-1]: 내부 번호 i가 맡은 구간의 합

    explicit Fenwick(int n) : n(n), data(n, 0) {}

    void add(int p, long long x) {             // a[p] += x
        for (int i = p + 1; i <= n; i += i & -i) data[i - 1] += x;
    }
    long long prefix(int r) const {            // a[0] + ... + a[r-1]
        long long s = 0;
        for (int i = r; i > 0; i -= i & -i) s += data[i - 1];
        return s;
    }
    long long sum(int l, int r) const {        // a[l] + ... + a[r-1]
        return prefix(r) - prefix(l);
    }
};

ACL도 add에서 p를 하나 늘린 뒤 p <= n인 동안 data[p-1]에 더하고 p += p & -p로 넘어가며, 내부 누적 합은 r > 0인 동안 data[r-1]을 더하고 r -= r & -r로 줄입니다. 공개 sum(l, r)은 내부 누적 합 두 개의 차입니다.

i & -i: 가장 낮은 1비트

2의 보수에서 -i는 ~i + 1입니다. i의 가장 낮은 1비트보다 아래는 모두 0이므로, 비트를 뒤집으면 그 자리들이 1이 되고, 1을 더하면 올림이 그 1비트 자리에서 멈춥니다. 그 결과 i와 -i가 공통으로 1인 비트는 가장 낮은 1비트 하나뿐입니다.

i      = 6 = 0110
-i         = 1010   (하위 4비트)
i & -i     = 0010 = 2

이 값을 lowbit(i)라고 부르겠습니다. 내부 번호 i의 칸은 내부 번호 (i - lowbit(i), i], 공개 인덱스로는 [i - lowbit(i), i)의 합을 들고 있습니다. 홀수 번호는 자기 원소 하나, 2의 거듭제곱 번호는 처음부터 자기까지 전체를 맡습니다. 내부 번호 0은 쓰지 않는데, 0 & -0이 0이라 0에서 시작한 루프는 끝나지 않기 때문입니다. ACL의 add가 맨 앞에서 p를 1 늘리는 것도 이 때문입니다.

원소 8개로 따라가기

공개 배열을 a = [5, 2, 9, -3, 4, 0, 7, 1](0-based)로 두고 칸마다 맡은 구간과 값을 적으면 다음과 같습니다.

내부 i 이진 lowbit 공개 구간 data[i-1]
1 0001 1 [0, 1) 5
2 0010 2 [0, 2) 7
3 0011 1 [2, 3) 9
4 0100 4 [0, 4) 13
5 0101 1 [4, 5) 4
6 0110 2 [4, 6) 4
7 0111 1 [6, 7) 7
8 1000 8 [0, 8) 25

누적 합 prefix(7) (= a[0] + … + a[6]):

i 더하는 칸 맡은 구간 누계 다음 i
7 (0111) data[6] = 7 [6, 7) 7 7 − 1 = 6
6 (0110) data[5] = 4 [4, 6) 11 6 − 2 = 4
4 (0100) data[3] = 13 [0, 4) 24 4 − 4 = 0

구간 [6,7), [4,6), [0,4)는 겹치지 않고 이어져서 정확히 [0,7)을 덮습니다. 가장 낮은 1비트를 하나씩 지우는 것은 [0, r)의 오른쪽 끝에서부터 블록을 하나씩 떼어 내는 것과 같습니다. 실제 합 5 + 2 + 9 − 3 + 4 + 0 + 7 = 24와 맞습니다.

구간 합 sum(2, 7): prefix(2)는 i = 2에서 data[1] = 7을 더하고 바로 끝나므로 7입니다. 따라서 24 − 7 = 17이고, 실제로 9 − 3 + 4 + 0 + 7 = 17입니다.

갱신 add(2, +10): 공개 위치 2는 내부 번호 3입니다.

i 고치는 칸 맡은 구간 다음 i
3 (0011) data[2]: 9 → 19 [2, 3) 3 + 1 = 4
4 (0100) data[3]: 13 → 23 [0, 4) 4 + 4 = 8
8 (1000) data[7]: 25 → 35 [0, 8) 8 + 8 = 16 > 8, 종료

표에서 공개 인덱스 2를 포함하는 구간은 i = 3, 4, 8 세 칸뿐이고, 루프는 정확히 그 칸들을 방문했습니다. lowbit를 더하면 올림이 생기면서 다음 번호의 lowbit가 더 높은 자리로 올라가고, 그 칸은 지금 칸의 구간을 품는 더 넓은 구간을 맡습니다. 갱신 뒤 prefix(7)은 data[6] + data[5] + data[3] = 7 + 4 + 23 = 34로, 앞의 24에서 10만큼 늘었습니다.

계산량

  • 누적 합: 반복마다 i의 1비트가 하나씩 사라집니다. 반복 횟수는 r의 1비트 수이고, r ≤ n이므로 ⌊log₂ n⌋ + 1을 넘지 않습니다.
  • 갱신: i에 lowbit(i)를 더하면 다음 번호의 lowbit는 적어도 두 배가 됩니다. n을 넘으면 멈추므로 반복은 ⌊log₂ n⌋ + 1회 이하입니다.
  • 구간 합: 누적 합 두 번이라 O(log n)입니다.
  • 공간: 길이 n 배열 하나, O(n)입니다.

이 분석은 위 루프에서 이끌어 낸 설명이고, 결론은 ACL 문서의 O(log n) 표기와 일치합니다.

초기값이 있을 때의 구축 비용

ACL 생성자의 O(n)은 모든 원소가 0인 구조를 만드는 비용입니다. 임의의 초기 배열을 넣으려고 add를 n번 부르면 O(n log n)이 됩니다.

선형 시간에 만드는 방법도 있습니다. ACL의 API에는 없는 방법이라 직접 구현해야 합니다. data를 a로 채운 뒤, i = 1부터 n까지 차례로 자기 값을 부모 칸 i + lowbit(i)(n 이하일 때)에 더합니다.

for (int i = 1; i <= n; i++) data[i - 1] = a[i - 1];
for (int i = 1; i <= n; i++) {
    int j = i + (i & -i);
    if (j <= n) data[j - 1] += data[i - 1];
}

i보다 작은 번호만 i에 값을 보내므로, i를 처리하는 시점에는 data[i-1]이 이미 완성되어 있습니다. 위의 a에 적용하면 [5, 7, 9, 13, 4, 4, 7, 25]로 표와 같은 값이 나옵니다.

실수하기 쉬운 지점

  • 빈 구간: sum(l, l)은 prefix(l) - prefix(l)이므로 0입니다. ACL 조건도 l == r을 허용합니다.
  • 범위: ACL 문서의 조건은 0 ≤ p < n, 0 ≤ l ≤ r ≤ n입니다. 직접 구현할 때 내부 번호 0을 루프에 넣으면 끝나지 않습니다.
  • 음수 변화량: 합에서는 add(p, -x)로 빼기도 그대로 됩니다.
  • 값 대입: 펜윅 트리는 a[p]를 따로 보관하지 않습니다. a[p] = v를 하려면 원래 값이 필요하므로, 원본 배열을 함께 들고 add(p, v - a[p])를 하거나, sum(p, p + 1)로 O(log n)에 현재 값을 복원해야 합니다.
  • 오버플로: 합의 절댓값은 최대 n × max|a[i]|까지 커집니다. n = 2×10⁵, |a[i]| ≤ 10⁹이면 2×10¹⁴로 32비트 정수를 넘으니 64비트가 필요합니다. ACL 문서는 정수 타입에서 오버플로가 나면 답을 2^bit로 나눈 나머지로 돌려준다고 적고 있습니다. 직접 구현할 때 C++의 부호 있는 정수 오버플로는 정의되지 않은 동작이므로 타입 선택을 처음부터 넉넉하게 해야 합니다. 자세한 내용은 정수 오버플로 글에 있습니다.

다른 자료구조와 비교

질의 점 갱신 메모리
누적 합 배열 O(1) O(n) n + 1
펜윅 트리 O(log n) O(log n) n
세그먼트 트리 O(log n) O(log n) 보통 n보다 많은 노드

갱신이 없다면 누적 합 배열이 더 간단하고 빠릅니다. 세그먼트 트리도 점 갱신과 구간 질의를 O(log n)에 처리하고, 최솟값·최댓값처럼 역연산이 없는 연산이나 지연 전파를 쓰는 구간 갱신까지 다룰 수 있습니다. 대신 구현과 저장 공간이 더 큽니다. 펜윅 트리가 모든 경우에 세그먼트 트리보다 빠르다고 단정할 근거는 없습니다. 실제 차이는 구현과 작업 부하에 따라 측정해야 합니다.

펜윅 트리의 구간 합은 prefix(r) - prefix(l)라는 뺄셈에 기대고 있습니다. 덧셈처럼 역원이 있는 연산이어야 이 방식이 통합니다. 최댓값은 결합 법칙은 성립하지만 빼서 앞부분을 지울 수 없으므로, 임의 구간 [l, r)의 최댓값은 같은 방법으로 얻지 못합니다. 누적 최댓값만 묻고 값이 커지기만 하는 경우처럼 조건을 붙인 변형은 있지만, 이 글의 범위는 정수 합까지입니다.

쓰임새: 다시 누적 빈도

초록이 말하는 원래 용도처럼, 기호 0…n−1의 출현 횟수를 세는 데 그대로 쓸 수 있습니다. 기호 s가 나올 때마다 add(s, 1), s보다 작은 기호의 누적 빈도는 sum(0, s)입니다. 같은 방식으로 “지금까지 본 값 중 x 이하는 몇 개인가”를 값 범위 위에서 세면 반전 수(inversion count) 같은 문제도 O(n log n)에 풀립니다. 값 범위가 크다면 좌표 압축으로 0…k−1에 먼저 대응시킵니다.

확인한 자료

모두 2026-10-27에 확인했습니다.

블로그로