Fenwick Tree: 바뀌는 배열의 구간 합

누적합과 차분 배열에서는 갱신을 모두 모은 뒤 질의했습니다. 이번에는 갱신 직후 바로 구간 합을 물어봅니다. 원래 배열과 각 칸이 담당하는 구간을 나란히 놓으면 idx & -idx가 단순한 비트 연산 요령이 아니라 구간을 나누는 규칙임을 볼 수 있습니다.

Fenwick Tree는 배열의 prefix 합을 빠르게 관리하는 자료구조입니다. Binary Indexed Tree, 줄여서 BIT라고도 부릅니다.

가장 대표적인 문제는 다음 형태입니다.

배열 a가 있다.
1. a[idx]에 값을 더한다.
2. 구간 [l, r]의 합을 빠르게 구한다.

누적합 배열만 있으면 구간 합은 O(1)이지만, 중간 값이 바뀔 때 누적합을 다시 고치는 데 O(n)이 걸립니다. Fenwick Tree는 값을 바꾸는 작업과 합을 묻는 작업을 모두 O(log n)에 처리합니다.

Segment Tree보다 할 수 있는 일은 좁지만, 구간 합처럼 prefix로 표현되는 문제에서는 코드가 짧고 빠릅니다.

prefix 합으로 생각하기

구간 합은 prefix 합 두 개로 바꿀 수 있습니다.

sum(l, r) = prefixSum(r) - prefixSum(l - 1)

그래서 Fenwick Tree는 prefixSum(x)를 빠르게 구하는 데 집중합니다. 각 칸은 배열의 한 구간 합을 저장하고, 여러 칸을 더해 원하는 prefix를 만듭니다.

Fenwick Tree는 보통 1-indexed로 구현합니다. 입력이 0-indexed라면 함수에 넣기 전에 idx + 1로 바꾸거나, wrapper에서 처리하면 됩니다.

lowbit

Fenwick Tree의 핵심은 가장 낮은 1비트만 남기는 lowbit(x) = x & -x입니다.

lowbit(x)는 x의 이진수에서 가장 낮은 1비트가 나타내는 값을 반환합니다.

x	이진수	lowbit(x)
1	0001	1
2	0010	2
3	0011	1
4	0100	4
6	0110	2
8	1000	8

Fenwick Tree의 tree[i]는 길이가 lowbit(i)인 구간의 합을 저장합니다. 정확히는 다음 구간입니다.

tree[i] = a[i - lowbit(i) + 1] + ... + a[i]

예를 들어 tree[8]은 lowbit(8) = 8이므로 a[1]부터 a[8]까지의 합을 담고, tree[6]은 lowbit(6) = 2이므로 a[5] + a[6]을 담습니다.

prefixSum

그림 크게 보기

prefixSum(idx)는 a[1] + ... + a[idx]를 구합니다. 현재 위치의 구간을 더한 뒤, 그 구간 바로 앞 위치로 이동합니다.

예를 들어 prefixSum(13)은 다음 칸들을 더합니다.

13 -> 12 -> 8 -> 0

tree[13]은 마지막 1개, tree[12]는 그 앞 4개, tree[8]은 그 앞 8개를 담당합니다. 합치면 1부터 13까지의 합이 됩니다.

add

a[idx]에 delta를 더할 때는 idx를 포함하는 Fenwick Tree 칸들을 모두 고쳐야 합니다.

prefixSum이 아래쪽으로 내려간다면, add는 위쪽으로 올라갑니다. idx += lowbit(idx)를 반복하면 현재 원소를 포함하는 더 큰 구간으로 이동합니다. idx = 0에서는 lowbit(0) = 0이라 루프가 끝나지 않으므로, add에는 1 이상의 인덱스만 넘깁니다.

같은 원소가 어떤 칸들을 바꾸는가

그림 크게 보기

Fenwick 담당 구간과 갱신 실험

초기 배열이 [1,2,3,4,5,6,7,8]이면 prefixSum(7)은 tree[7] + tree[6] + tree[4] = 7 + 11 + 10 = 28입니다. 세 칸이 담당하는 구간은 [7,7], [5,6], [1,4]로 서로 겹치지 않습니다.

3번 원소에 5를 더하면 tree[3], tree[4], tree[8]만 바뀝니다. 모두 3번 원소를 포함하는 구간입니다. 7까지 합을 다시 물으면 33이 나옵니다. 질의는 겹치지 않는 구간을 모으고, 갱신은 해당 원소를 포함한 구간을 고칩니다. 화살표 방향을 외우기보다 이 차이를 먼저 확인하세요.

데모는 갱신이 진행되는 중간 상태도 보여줍니다. 그 상태에서는 질의를 끼워 넣지 않으며 모든 갱신 칸을 고친 뒤 다시 합을 계산합니다. 음수 덧셈도 합 질의에는 문제가 없지만, 아래 lowerBound는 모든 원소가 비음수여야 사용할 수 있습니다.

전체 구현

아래 구현은 1-indexed Fenwick Tree입니다. add에는 1..n, prefixSum에는 0..n, rangeSum에는 1 <= l <= r <= n을 전달합니다. 원소별 add로 초기화하므로 빌드는 O(n log n), 이후 갱신과 질의는 O(log n)입니다.

코드 환경: 일반 C++17 학습용. 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 공통 코드와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

#include <vector>
using namespace std;

struct FenwickTree {
    int n;
    vector<long long> tree;

    FenwickTree(int n) : n(n), tree(n + 1, 0) {}

    FenwickTree(const vector<long long>& values) {
        n = (int)values.size();
        tree.assign(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            add(i + 1, values[i]);
        }
    }

    void add(int idx, long long delta) {
        while (idx <= n) {
            tree[idx] += delta;
            idx += idx & -idx;
        }
    }

    long long prefixSum(int idx) const {
        long long result = 0;
        while (idx > 0) {
            result += tree[idx];
            idx -= idx & -idx;
        }
        return result;
    }

    long long rangeSum(int l, int r) const {
        return prefixSum(r) - prefixSum(l - 1);
    }

    void setValue(int idx, long long oldValue, long long newValue) {
        add(idx, newValue - oldValue);
    }
};

setValue처럼 값을 대입하는 연산을 만들 때는 기존 값을 알아야 합니다. Fenwick Tree 자체는 “얼마를 더할지”를 받는 구조이므로, 원본 배열을 따로 들고 있으면 더 편합니다.

lower_bound

모든 값이 음수가 아니면, Fenwick Tree로 “prefix 합이 처음으로 target 이상이 되는 위치”도 찾을 수 있습니다.

다음 멤버 함수를 위 FenwickTree 안에 추가합니다. target <= 0은 1, 전체 합보다 큰 target은 n + 1을 반환합니다. 값별 빈도를 저장했다면 lowerBound(k)로 k번째 원소의 값 인덱스를 찾을 수 있습니다.

int lowerBound(long long target) const {
    if (target <= 0) return 1;
    if (target > prefixSum(n)) return n + 1;

    int idx = 0;
    int bit = 1;
    while (bit <= n / 2) bit <<= 1;

    for (; bit > 0; bit >>= 1) {
        int next = idx + bit;
        if (next <= n && tree[next] < target) {
            idx = next;
            target -= tree[next];
        }
    }
    return idx + 1;
}

이 함수는 Fenwick Tree 위에서 이진 탐색을 하는 느낌입니다. 왼쪽부터 구간을 크게 붙여 보면서 target에 아직 못 미치면 그 구간을 통째로 건너뜁니다.

주의할 점은 값이 음수일 수 있으면 prefix 합이 단조 증가하지 않는다는 것입니다. 그 경우에는 이 방식으로 lower_bound를 할 수 없습니다.

로컬 연습: 점 덧셈과 구간 합

배열의 점 덧셈과 닫힌 구간 합을 처리하세요. 이 연습은 본문의 Fenwick 구현과 같은 1-based 인덱스를 사용합니다.

입력: N Q, N개 초기 값, Q개 연산. A i delta는 점 덧셈, S l r은 [l,r] 합입니다. 1 <= N <= 200000, 0 <= Q <= 200000, |초기 값|,|delta| <= 10^9, 1 <= l <= r <= N입니다.

출력: S 연산의 답을 한 줄씩 출력합니다.

예시

5 5
1 2 3 4 5
S 1 5
A 3 -5
S 2 4
A 1 10
S 1 1

15
4
11

확인 방법: 작은 배열을 직접 갱신·합산하는 기준 풀이와 비교합니다. i=1, i=N, l=r, 음수 갱신을 검사합니다. 실제 Fenwick 내부 함수에 index 0을 넣으면 lowbit 진행이 멈추므로 wrapper에서 경계를 맞춥니다.

완성 파일로 실행하고 확인하기

C++17 전체 예제 내려받기

c++ -std=c++17 -O2 fenwick-tree.cpp -o lesson
./lesson < input.txt

기본 모드는 위 연습의 A i delta, S l r을 처리하고 15, 4, 11을 출력합니다. 본문의 FenwickTree에 lowerBound 멤버를 붙여 하나의 완성 파일로 조합했습니다. 공개 함수는 설명한 인덱스 계약을 따르며, 실행 파일의 입력부는 0이나 범위 밖 인덱스를 거부합니다.

순위 탐색은 별도 모드로 실행합니다.

./lesson --select < select-input.txt

이 모드는 N Q, N개의 비음수 값, Q개의 target을 순서대로 읽고 각 lowerBound(target)을 출력합니다. 1 ≤ N ≤ 200000, 0 ≤ Q ≤ 200000, 0 ≤ 값 ≤ 10^9, |target| ≤ 10^15입니다. 갱신은 하지 않습니다. target≤0은 1, 전체 합보다 크면 N+1입니다.

5 4
2 0 3 1 0
0 2 3 7

결과는 1,1,3,6입니다. 합 질의에서 허용하는 음수 갱신을 이 모드까지 그대로 허용하면 안 됩니다. 작은 배열은 선형으로 누적합을 읽어 처음 target 이상이 되는 위치와 비교합니다.

기존 Fenwick 코드 노트도 함께 볼 수 있습니다. 기존 기록의 코드·작성 시점은 유지하며, 이 강의의 다운로드 파일을 현재 실습 기준으로 사용합니다.