배열에 부분 합 저장하기
펜윅 트리는 각 위치에 일정한 구간의 합을 저장한다. 한 원소가 여러 부분 합에 포함되지만 모든 접두 합을 따로 저장하는 방식보다 갱신할 항목이 적다. 원래 배열의 값이 바뀌는 상황에서도 접두 합을 반복해서 계산할 수 있도록 구성한다.
인덱스의 가장 낮은 비트
1부터 시작하는 대표적인 구현에서 i번 항목은 i−lowbit(i)+1부터 i까지의 합을 저장한다. lowbit(i)는 이진수에서 가장 낮은 1비트가 나타내는 값이다. 예를 들어 12의 이진 표현은 1100이고 lowbit(12)=4이므로 12번 항목은 9번부터 12번 원소의 합을 담는다.
질의와 변경의 방향
접두 합을 구할 때는 현재 항목의 합을 더한 뒤 인덱스에서 lowbit 값을 빼며 이동한다. 한 원소에 Δ를 더할 때는 관련 항목에 Δ를 반영하고 인덱스에 lowbit 값을 더하며 이동한다. 값을 새 값으로 지정하려면 기존 값과의 차이를 구해 증가 갱신으로 반영할 수 있다.
일반 구간과 연산의 한계
l부터 r까지의 합은 r까지의 접두 합에서 l−1까지의 접두 합을 빼면 된다. 합에는 이러한 차 연산이 가능하지만 최솟값 두 개를 빼서 구간 최솟값을 얻을 수는 없다. 따라서 합을 위한 기본 구현을 임의의 연산과 갱신에 그대로 적용하면 안 된다.