펜윅트리

펜윅트리

배열의 구간합을 구하는 데는, 구간 트리를 활용할 수 도 있지만 그 구현이 복잡해 조금 더 단순한 형태인 펜윅트리를 사용하는 것이 더 좋다.
펜윅트리란 배열의 첫 몇 개의 원소인 부분합을 활용하면 구간합도 빠르게 계산할 수 있다는 원리에서 출발한 구조이다.

펜윅트리의 구현

펜윅트리를 실제로 구현하기 위해서는 이진수를 활용한다. 배열을 구간 트리처럼 절반씩 나눠갈 때 나눈 구간 중 절반은 다른 구간합을 활용해 계산할 수 있기 때문에 굳이 저장할 필요가 없다. 따라서 매번 절반씩 나눠가면서 한 쪽만 저장하게 되면 총 n개의 구간합만 저장하면 모든 구간합을 구할 수 있다.
i부터 j까지의 구간합을 구한다고 하면 j의 부분합에서 i의 부분합을 빼면된다. 만약 i나 j의 부분합이 트리에 저장되어 있지 않다면 이는 저장되어 있는 값을 활용해서 구해야되는데 이 때 이진수가 활용된다.

부분합을 위한 이진수 활용

특정 인덱스의 부분합을 구하기 위해 더해줘야 하는 구간합들은 그 인덱스의 이진수 표현을 보면 알 수 있다. 그 인덱스의 마지막 비트를 지워가면서 마지막 비트가 첫 비트가 될 때까지 더해주면 부분합을 구할 수 있다.

갱신을 위한 이진수 활용

배열의 특정 원소 값을 변경하거나, 처음 트리를 만들 때 갱신을 위한 함수가 필요한데, 이 과정에서도 이진수가 활용된다. 특정 숫자가 갱신된다고 하면, 그 숫자가 포함된 모든 구간에 대한 값을 바꿔줘야 한다. 이 구간들을 구하는 방법은 바뀐 부분의 인덱스에 대하여 마지막 비트를 한번씩 더해가면서 트리의 크기보다 커지기 전 까지 갱신해주면 된다.