펜윅 트리

[1. 개요]

구간 합을 빠르게 구하기 위한 구간 트리의 상위 버전으로 볼 수 있는 자료구조

구간 합 대신 부분 합만을 빠르게 계산 할 수 있는 자료 구조를 만들어도 구간 합을 계산 할 수 있다.

=> 구간 트리가 미리 계산해 저장하는 정보의 상당수가 필요 없다.

하나의 긴 구간 밑에 두 개의 작은 구간이 있을 때, 이 두 구간 중

오른쪽 구간은 항상 지워도 된다.

=> 필요한 구간의 수는 정확하게 N 개이다.

=> 구간 트리가 보통 4N 개가 필요하다고 했을 때, 메모리를 조금이라도 덜 사용한다.

또한, 각 구간이 포함하는 오른쪽 끝 원소들이 모두 다르다.

=> 구간 트리에서 (0, 7) (4, 7) 등 끝나는 구간이 같은 것이 다수 존재함.

[2. 구현]

tree[i] = 오른쪽 끝 위치가 A[i] 인 구간의 합

psum[pos] 를 계산하려면, pos 에서 끝나는 구간의 합 tree[pos] 를 답에 더해야 한다.

=> O(logn) 개의 구간 합만 있으면 된다.

pos 에서 끝나는 구간 다음으로 더해야 할 구간을 찾는 방법

=> tree 의 노드를 1 부터 시작 ==> 트리 구현을 위한 메모리는 N+1 => 결국 N 이라 볼 수 있다.

=> 숫자의 이진수 표현을 이용

구간 합 sum() 구현

펜윅 트리는 구간 트리처럼 모든 구간에 대해 답을 계산하지 않으므로

O(n) 에 초기화하는 것이 불가능하다.

펜윅 트리에서 배열의 값을 변경하는 것은 해당 위치의 값에 숫자를 더하고 빼는 것으로 구현

ex) A[5] 를 3 늘리고 싶다 => A[5] 를 포함하는 모든 구간의 구간 합들을 3씩 늘려주도록 한다.

맨 오른쪽에있는 1인 비트를 자기 자신에게 더해주는 연산을 반복하면,

해당 위치를 포함하는 모든 구간들을 만날 수 있다.

[3. 코드]

test_kernelv2