240723 펜윅 트리(Fenwick Tree): 효율적인 구간 합과 업데이트

Jongleee·2024년 7월 23일

목록 보기

632/737

개요

펜윅 트리(Fenwick Tree), 혹은 바이너리 인덱스 트리(Binary Indexed Tree, BIT)는 구간 합 쿼리와 요소 업데이트를 효율적으로 수행할 수 있는 자료구조입니다. 이 자료구조는 주로 배열과 관련된 문제에서 많이 사용되며, 시간 복잡도가 O(log n)으로 매우 효율적입니다.

사용하는 이유

펜윅 트리는 구간 합을 빠르게 계산해야 하는 문제에서 매우 유용합니다. 예를 들어, 배열의 특정 구간의 합을 빈번하게 구하고 배열의 값도 자주 갱신해야 하는 경우, 펜윅 트리는 이를 효율적으로 처리할 수 있습니다. 전통적인 방법으로는 구간 합 계산에 O(n), 업데이트에 O(1)의 시간이 소요되지만, 펜윅 트리를 사용하면 이 둘을 모두 O(log n)으로 줄일 수 있습니다.

기본 개념

펜윅 트리는 내부적으로 배열을 사용하여 트리 구조를 시뮬레이션합니다. 배열의 인덱스를 이진수로 표현하여 특정 비트 연산을 통해 부모 노드와 자식 노드를 결정합니다. 이 방식은 트리 구조를 단순한 배열로 구현할 수 있게 해줍니다.

구현

초기화

펜윅 트리는 배열의 크기를 정하여 초기화합니다. 예를 들어, 크기 n의 배열을 다루기 위해 길이 n + 1의 배열을 생성합니다. 이는 인덱스 1부터 n까지의 요소를 사용하기 위함입니다.

public class FenwickTree {
    private int[] tree;
    private int size;

    public FenwickTree(int size) {
        this.size = size;
        this.tree = new int[size + 1];
    }

    public void update(int index, int value) {
        while (index <= size) {
            tree[index] += value;
            index += index & -index;
        }
    }

    public int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= index & -index;
        }
        return sum;
    }

    public int rangeQuery(int left, int right) {
        return query(right) - query(left - 1);
    }
}

업데이트

업데이트 함수는 배열의 특정 인덱스에 값을 추가합니다. 인덱스에 해당하는 노드를 업데이트하고, 그 노드의 부모 노드들도 업데이트합니다.

public void update(int index, int value) {
    while (index <= size) {
        tree[index] += value;
        index += index & -index;
    }
}

쿼리

쿼리 함수는 1부터 주어진 인덱스까지의 구간 합을 계산합니다. 인덱스의 부모 노드로 이동하며 합을 누적합니다.

public int query(int index) {
    int sum = 0;
    while (index > 0) {
        sum += tree[index];
        index -= index & -index;
    }
    return sum;
}

구간 쿼리

구간 쿼리 함수는 특정 범위의 합을 구합니다. 이는 두 개의 쿼리 결과를 뺄셈하여 구할 수 있습니다.

public int rangeQuery(int left, int right) {
    return query(right) - query(left - 1);
}

예제

public class FenwickTreeExample {
    public static void main(String[] args) {
        // 크기 10의 펜윅 트리 초기화
        FenwickTree fenwickTree = new FenwickTree(10);

        // 인덱스 3에 5를 추가
        fenwickTree.update(3, 5);

        // 인덱스 7에 2를 추가
        fenwickTree.update(7, 2);

        // 인덱스 1부터 7까지의 합을 구함
        System.out.println(fenwickTree.rangeQuery(1, 7));  // 출력: 7
    }
}