펜윅 트리와 세그먼트 트리는 코딩테스트에서 같이 언급되다 보니 입문자가 더 헷갈리기 쉬운 조합입니다. 둘 다 구간 합, 업데이트 같은 문제에 나온다고 하니 대체 뭐가 다른지 애매해지고, 결국 둘 다 어렵게 느껴지기도 합니다.
이번 글에서는 두 구조를 정의 나열로 비교하지 않고, 언제는 펜윅이 더 가볍고, 언제는 세그먼트 트리가 더 일반적이고 강한 선택인지 중심으로 설명하겠습니다.
둘은 왜 같이 자주 나오나
둘 다 배열에 대해 부분합을 빠르게 구하고, 중간 업데이트도 버티게 만들려는 구조입니다. 즉 누적합의 약점인 “업데이트가 잦으면 다시 계산 비용이 크다”는 문제를 해결하려는 점에서 출발이 같습니다.
그래서 코딩테스트에서 구간 합 + 업데이트 문제가 나오면 보통 둘 중 하나를 후보로 생각하게 됩니다.
펜윅 트리는 왜 더 가볍게 느껴질까
펜윅 트리는 binary indexed tree라고도 부르는데, 누적합을 비트 단위 구간으로 쪼개 저장합니다. 각 인덱스가 특정 길이의 부분합을 들고 있어서, prefix sum을 빠르게 합치고 update도 빠르게 전파할 수 있습니다.
세그먼트 트리보다 구현 길이가 짧고, 메모리 구조도 비교적 단순한 편이라 “구간 합 + 점 업데이트” 같은 문제에서는 입문자가 먼저 고려해 보기 좋은 구조입니다.
def update(i, delta):
while i <= n:
tree[i] += delta
i += i & -i
def prefix_sum(i):
s = 0
while i > 0:
s += tree[i]
i -= i & -i
return s입문자가 많이 헷갈리는 부분은 i & -i입니다. 이건 현재 인덱스가 담당하는 구간 크기를 나타내는 비트 패턴이라고 보면 됩니다. 즉 펜윅 트리는 비트 연산으로 상위 구간, 하위 구간을 빠르게 오가도록 설계된 구조입니다.
세그먼트 트리는 왜 더 일반적일까
세그먼트 트리는 배열을 구간 단위로 나눈 트리 구조라서, 합뿐 아니라 최소값, 최대값, 여러 종류의 구간 연산으로 확장하기가 더 자연스럽습니다. 즉 문제 범위가 넓어질수록 세그먼트 트리가 더 일반적인 해법이 됩니다.
반면 펜윅 트리는 더 가볍지만, 다루는 연산 종류 면에서는 세그먼트 트리보다 제한적인 경우가 많습니다. 그래서 둘은 경쟁자라기보다 적용 범위가 조금 다른 도구라고 보는 편이 정확합니다.
문제에서 어떤 신호가 보이면 무엇을 고를까
- 구간 합 + 점 업데이트 위주이고 구현을 가볍게 가고 싶다 → 펜윅 트리 우선 고려
- 최솟값/최댓값/복합 구간 연산까지 확장 가능성이 있다 → 세그먼트 트리 고려
- 좌표 압축과 함께 큰 인덱스 범위를 다뤄야 한다 → 둘 다 후보가 될 수 있음
- 누적합만으로 충분한지 먼저 보고, 부족할 때만 둘 중 하나로 올라간다
즉 먼저 누적합으로 충분한지 보고, 그다음 구간 업데이트/구간 질의가 같이 많다면 펜윅 또는 세그트리로 올라가는 식이 자연스럽습니다.
헷갈리는 포인트
- 펜윅 트리는 더 짧게 구현되지만 만능은 아니다
- 세그먼트 트리는 무겁지만 더 일반적인 구조다
- 둘 다 누적합의 확장처럼 볼 수 있지만, 문제 범위가 다르다
- 선택 기준은 “어느 쪽이 더 고급인가”가 아니라 “문제가 무엇을 요구하는가”다
누적합 감각은 누적합 글, 더 일반적인 구간 구조는 세그먼트 트리 글과 이어서 보면 훨씬 잘 연결됩니다.
마무리
펜윅 트리와 세그먼트 트리는 모두 구간 문제를 버티게 만드는 구조지만, 펜윅은 더 가볍고 세그먼트 트리는 더 일반적입니다.
즉 구간 합 중심의 가벼운 문제인지, 더 넓은 구간 연산까지 커질 문제인지를 먼저 보면 둘의 선택 기준이 훨씬 분명해집니다.
