펜윅 트리 (Binary Indexed Tree)

펜윅 트리란

펜윅 트리(Fenwick Tree, BIT)는 점 업데이트 + 구간 합 쿼리를 O(log N)에 처리하는 자료구조입니다. 세그먼트 트리보다 구현이 간단하고 메모리 효율이 높습니다.

핵심 아이디어: 인덱스 i의 최하위 비트(LSB)를 이용해 구간 합을 저장합니다.

인덱스(1-based): 1  2  3  4  5  6  7  8
LSB:             1  2  1  4  1  2  1  8
tree[i]가 담당: [1] [1,2] [3] [1,4] [5] [5,6] [7] [1,8]

기본 구현 (1-based 인덱스)

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

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

    // i번 위치에 val 더하기
    void update(int i, long long val) {
        for (; i <= n; i += i & (-i))  // LSB 더하기
            tree[i] += val;
    }

    // [1, i] 구간 합
    long long query(int i) {
        long long sum = 0;
        for (; i > 0; i -= i & (-i))   // LSB 빼기
            sum += tree[i];
        return sum;
    }

    // [l, r] 구간 합
    long long query(int l, int r) {
        return query(r) - query(l - 1);
    }

    // 초기 배열로 O(N) 구성
    FenwickTree(vector<int>& arr) : n(arr.size()), tree(arr.size() + 1, 0) {
        for (int i = 0; i < n; i++)
            update(i + 1, arr[i]);
    }
};

활용 예시: 구간 합 쿼리

int main() {
    vector<int> arr = {3, 2, -1, 6, 5, 4, -3, 3, 7, 2};
    FenwickTree bit(arr);

    cout << bit.query(1, 5);   // 15 (3+2-1+6+5)
    bit.update(3, 10);          // arr[3] += 10 → arr[3] = 9
    cout << bit.query(1, 5);   // 25
}

구간 업데이트 + 점 쿼리 (역할 반전)

차분 배열을 이용하면 구간 업데이트도 O(log N)으로 처리합니다.

class RangeFenwick {
    FenwickTree bit;
public:
    RangeFenwick(int n) : bit(n) {}

    // [l, r] 구간에 val 더하기
    void rangeUpdate(int l, int r, long long val) {
        bit.update(l, val);
        bit.update(r + 1, -val);
    }

    // i번째 값 쿼리
    long long pointQuery(int i) {
        return bit.query(i);
    }
};

2D 펜윅 트리

2차원 배열의 부분 합을 O(log N × log M)에 처리합니다.

class FenwickTree2D {
    int n, m;
    vector<vector<long long>> tree;

public:
    FenwickTree2D(int n, int m) : n(n), m(m), tree(n + 1, vector<long long>(m + 1, 0)) {}

    void update(int x, int y, long long val) {
        for (int i = x; i <= n; i += i & (-i))
            for (int j = y; j <= m; j += j & (-j))
                tree[i][j] += val;
    }

    long long query(int x, int y) {
        long long sum = 0;
        for (int i = x; i > 0; i -= i & (-i))
            for (int j = y; j > 0; j -= j & (-j))
                sum += tree[i][j];
        return sum;
    }

    // (x1,y1) ~ (x2,y2) 직사각형 합
    long long query(int x1, int y1, int x2, int y2) {
        return query(x2, y2) - query(x1 - 1, y2)
             - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
    }
};

k번째 원소 찾기

// BIT에서 k번째 원소 위치 O(log N)
int kth(int k) {
    int pos = 0;
    for (int pw = 1 << (int)log2(n); pw > 0; pw >>= 1) {
        if (pos + pw <= n && tree[pos + pw] < k) {
            pos += pw;
            k   -= tree[pos];
        }
    }
    return pos + 1;
}

세그먼트 트리 vs 펜윅 트리

항목	펜윅 트리	세그먼트 트리
구현 복잡도	낮음	높음
메모리	O(N)	O(4N)
점 업데이트 + 구간 합	O(log N)	O(log N)
구간 최솟값/최댓값	❌	✅
구간 업데이트 + 구간 합	lazy 필요	lazy 가능

정리

• i & (-i): 최하위 비트(LSB) 추출 — BIT의 핵심 연산
• 점 업데이트 + 구간 합에 특화, 세그먼트 트리보다 2~4배 빠름
• 차분 배열 BIT로 구간 업데이트 + 점 쿼리 지원
• 2D BIT로 직사각형 합 쿼리 O(log² N)