펜윅 트리 (Fenwick tree)?펜윅 트리 또는 Binary indexed tree는 prefix sum array의 변형으로 볼 수 있습니다. 이 자료구조는 구간의 합을 구하는 연산과 배열의 값을 변경하는 연산을 각각 O(logN)에 처리할 수 있습니다. 펜윅 트리의 이점은 구간의 합을 구하는 쿼리 중에도 효과적으로 배열의 값을 변경할 수 있다는 것이고 이 것은 일반적인 prefix sum array로는 처리하지 못합니다.구조tree라는 이름에서 알 수 있듯이 1차원 배열로 쉽게 표현할 수 있습니다. 구현의 용이성을 위해 펜윅 트리에서는 배열의 인덱스를 0이 아닌 1부터 시작합니다. k는 배열의 인덱스입니다. p(k)를 k를 나누는 가장 큰 2의 거듭제곱으로 정의합니다. 이진수에서 가장 우측에 존..