트리 배열(Fenwick Tree 또는 Binary Indexed Tree, BIT)는 동적 배열에서 구간 합과 단일 요소 갱신을 매우 효율적으로 처리할 수 있도록 설계된 자료구조입니다. 이 구조는 O(log n) 시간 내에 전위 합(prefix sum)을 계산하고, 특정 위치의 값을 수정할 수 있어 빈번한 갱신과 질의가 필요한 문제에서 큰 성능 이점을 제공합니다.

기본 원리

트리 배열은 1-기반 인덱스를 사용하는 것이 일반적이며, 보조 배열 tree를 통해 원본 배열의 부분합을 관리합니다. 각 인덱스 i에서 tree[i]는 특정 범위의 누적합을 저장하는데, 그 범위는 이진 표현에서 가장 오른쪽에 있는 1비트의 위치에 따라 결정됩니다.

lowbit 연산

핵심이 되는 연산은 다음과 같습니다:

int lowbit(int x) {
    return x & (-x);
}

예를 들어, x = 12(이진수 1100)인 경우, lowbit(12)는 4를 반환합니다. 이 값은 해당 인덱스가 포함하는 구간의 길이를 의미합니다.

부분합 관리 방식

• 갱신(add): 인덱스 i에 값 delta를 더할 때, i에서 시작해 i += lowbit(i)를 반복하며 모든 관련 노드를 갱신합니다.
• 쿼리(sum): 인덱스 1부터 i까지의 합을 구할 때, i에서 시작해 i -= lowbit(i)를 반복하며 해당 노드들의 값을 누적합니다.

구현 예시 (C++)

다음은 트리 배열의 기본 구현입니다:

#include <iostream>
#include <vector>

class BIT {
public:
    int size;
    std::vector<long long> tree;

    explicit BIT(int n) : size(n), tree(n + 1, 0) {}

    // 가장 낮은 비트 1의 값을 추출
    static int extractLowestBit(int x) {
        return x & (-x);
    }

    // 특정 위치에 값 추가
    void update(int index, long long delta) {
        for (int i = index; i <= size; i += extractLowestBit(i)) {
            tree[i] += delta;
        }
    }

    // 1부터 index까지의 누적합 계산
    long long prefixSum(int index) {
        long long result = 0;
        for (int i = index; i > 0; i -= extractLowestBit(i)) {
            result += tree[i];
        }
        return result;
    }

    // [left, right] 구간 합 계산
    long long rangeSum(int left, int right) {
        if (left > right) return 0;
        return prefixSum(right) - prefixSum(left - 1);
    }
};

// 사용 예제
int main() {
    std::vector<int> data = {0, 1, 3, 5, 7, 9}; // 1-based indexing
    int n = 5;
    BIT bitArray(n);

    // 초기값 삽입
    for (int i = 1; i <= n; ++i) {
        bitArray.update(i, data[i]);
    }

    std::cout << "Prefix sum up to 3: " << bitArray.prefixSum(3) << "\n"; // 1+3+5 = 9

    bitArray.update(2, 2); // data[2] += 2 → now 5
    std::cout << "Prefix sum up to 3 after update: " << bitArray.prefixSum(3) << "\n"; // 1+5+5 = 11

    std::cout << "Sum from index 2 to 4: " << bitArray.rangeSum(2, 4) << "\n"; // 5+5+7 = 17

    return 0;
}

시간 및 공간 복잡도

• 단일 갱신 및 쿼리: O(log n)
• 초기화: 각 요소를 순차적으로 삽입하면 O(n log n)
• 공간 복잡도: O(n)

트리 배열은 구현이 간단하면서도 강력한 기능을 제공하므로, 역순쌍 개수 세기, 동적 순위 계산, 2D 구간 합 등 다양한 응용 문제에서 유용하게 사용됩니다.