펜윅 트리(Fenwick Tree), 또는 바이너리 인덱스 트리(Binary Indexed Tree, BIT)는 배열의 특정 원소들에 대한 구간 합을 효율적으로 계산하기 위한 자료 구조입니다. 특히, 원소의 갱신과 구간 합 계산을 빠르게 수행할 수 있어 알고리즘 문제 풀이에서 유용하게 활용됩니다.

펜윅 트리의 주요 특징:

1. 트리 구조: 일반적으로 배열 형태로 구현되지만, 펜윅 트리는 트리 구조로 간단하게 표현됩니다.
2. 이진 인덱스: 인덱스가 이진 표현으로 되어 있어, 각 노드는 상위 노드로 이동하면서 필요한 연산을 수행합니다.
3. 구간 합 계산: 원소의 갱신과 구간 합을 효율적으로 계산할 수 있습니다.
4. O(log n) 시간 복잡도: 원소의 갱신과 구간 합 계산 모두 O(log n)의 시간 복잡도를 가집니다.

펜윅 트리의 활용 예시:

• 누적 합 계산: 배열의 각 원소까지의 누적 합을 펜윅 트리를 사용하여 효율적으로 계산할 수 있습니다.
• 구간 합 계산: 특정 구간의 합을 빠르게 계산하거나 구간 내의 최솟값, 최댓값을 구할 때 활용됩니다.
• 배열 갱신: 배열의 특정 원소의 값을 갱신할 때 펜윅 트리를 사용하여 누적 합을 업데이트할 수 있습니다.

파이썬 코드를 통해 펜윅 트리를 예시로 살펴보겠습니다. 다음은 펜윅 트리를 구현하여 누적 합을 계산하는 코드입니다.

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, index, value):
        while index <= self.n:
            self.tree[index] += value
            index += index & -index

    def query(self, index):
        result = 0
        while index > 0:
            result += self.tree[index]
            index -= index & -index
        return result

# 원본 배열
arr = [3, 2, -1, 6, 5, 4, -3, 3, 7, 2]
n = len(arr)

fenwick = FenwickTree(n)
for i in range(1, n + 1):
    fenwick.update(i, arr[i - 1])

# 특정 구간의 누적 합 계산
left, right = 2, 7
cumulative_sum = fenwick.query(right) - fenwick.query(left - 1)
print(f"인덱스 {left}부터 {right}까지의 누적 합:", cumulative_sum)

이 코드는 펜윅 트리를 구현하여 배열의 누적 합을 계산하는 예시입니다. 펜윅 트리를 사용하여 효율적으로 구간 합을 계산합니다.