[C++로 배우는 알고리즘과 자료구조 심화] Day 3: 펜윅 트리 (Fenwick Tree, Binary Indexed Tree)

펜윅 트리 (Fenwick Tree, Binary Indexed Tree)

펜윅 트리(BIT, Fenwick Tree)는 배열의 구간 합을 효율적으로 계산하고 업데이트할 수 있는 자료구조입니다. 세그먼트 트리와 유사하지만, 구현이 더 간단하고 메모리 사용량이 적습니다.

펜윅 트리의 주요 특징

1. 시간 복잡도:
   • 업데이트: (O(\log n))
   • 쿼리: (O(\log n))
2. 구현 방법:
   • 트리의 각 노드는 배열의 특정 구간에 대한 정보를 저장합니다.
   • 이진수의 비트 연산을 활용하여 구간을 관리합니다.

펜윅 트리의 기본 연산

1. 업데이트 (Update): 특정 인덱스의 값을 업데이트합니다.
2. 쿼리 (Query): 특정 인덱스까지의 구간 합을 계산합니다.

펜윅 트리의 구현

다음은 C++로 펜윅 트리를 구현한 예제입니다. 구간 합을 구하고 구간 값을 업데이트하는 연산을 포함합니다.

 

펜윅 트리 클래스 정의

#include <iostream>
#include <vector>

// 펜윅 트리 클래스 정의
class FenwickTree {
public:
    FenwickTree(int size);
    void update(int index, int value); // 값 업데이트 함수
    int query(int index); // 구간 합 쿼리 함수
    int rangeQuery(int left, int right); // 구간 합 범위 쿼리 함수

private:
    std::vector<int> tree; // 펜윅 트리 배열
    int n; // 원본 배열의 크기
};

// 펜윅 트리 생성자 정의
FenwickTree::FenwickTree(int size) {
    this->n = size;
    tree.resize(size + 1, 0);
}

// 값 업데이트 함수 정의
void FenwickTree::update(int index, int value) {
    index++;
    while (index <= n) {
        tree[index] += value;
        index += index & -index; // 다음 인덱스로 이동
    }
}

// 구간 합 쿼리 함수 정의
int FenwickTree::query(int index) {
    int sum = 0;
    index++;
    while (index > 0) {
        sum += tree[index];
        index -= index & -index; // 이전 인덱스로 이동
    }
    return sum;
}

// 구간 합 범위 쿼리 함수 정의
int FenwickTree::rangeQuery(int left, int right) {
    return query(right) - query(left - 1);
}

 

사용 예제

int main() {
    int size = 10;
    FenwickTree fenwickTree(size);

    // 배열의 각 요소를 업데이트
    std::vector<int> data = {3, 2, -1, 6, 5, 4, -3, 3, 7, 2};
    for (int i = 0; i < size; ++i) {
        fenwickTree.update(i, data[i]);
    }

    // 구간 합 쿼리
    std::cout << "인덱스 0부터 5까지의 구간 합: " << fenwickTree.rangeQuery(0, 5) << std::endl; // 3 + 2 - 1 + 6 + 5 + 4 = 19
    std::cout << "인덱스 3부터 8까지의 구간 합: " << fenwickTree.rangeQuery(3, 8) << std::endl; // 6 + 5 + 4 - 3 + 3 + 7 = 22

    // 값 업데이트
    fenwickTree.update(3, 2); // 인덱스 3의 값을 2만큼 증가
    std::cout << "인덱스 0부터 5까지의 구간 합 (업데이트 후): " << fenwickTree.rangeQuery(0, 5) << std::endl; // 3 + 2 - 1 + 8 + 5 + 4 = 21

    return 0;
}

 

설명

1. 펜윅 트리 클래스:
   • update: 특정 인덱스의 값을 업데이트합니다. 이진수의 비트 연산을 활용하여 다음 인덱스로 이동합니다.
   • query: 특정 인덱스까지의 구간 합을 계산합니다. 이진수의 비트 연산을 활용하여 이전 인덱스로 이동합니다.
   • rangeQuery: 특정 구간 [left, right]의 구간 합을 계산합니다. 두 개의 쿼리 결과를 활용하여 구간 합을 계산합니다.
2. 사용 예제:
   • 초기 배열을 업데이트하고, 구간 합을 쿼리하는 예제를 포함합니다.
   • 값 업데이트 후, 구간 합이 변경되는지 확인합니다.

펜윅 트리의 기본 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 4: 이면 탐색 트리(Treap)"에 대해 학습하겠습니다.