펜윅트리1 Fenwick Tree (펜윅 트리, Binary Indexed Tree = BIT) 배열에서 어느 구간의 구간합을 구한다고 하자. 누적합을 저장한 배열을 사용하면 특정 구간의 구간합을 단순히 두 위치의 값을 빼줌으로 상수 시간에 쉽게 구할 수 있다. 그러나 만약 배열의 값이 자주 바뀐다면 문제가 생긴다. 만약 원래 배열의 k번째 값이 변경된다면 누적합을 저장한 배열에서 k번째와 그 이후의 값들은 모두 변경해주어야 한다. 최악의 경우엔 누적 값을 저장한 배열의 n개의 값들을 다 변경해주어야 한다. 데이터의 양이 많으면서 데이터의 값이 자주 수정된다면 누적합은 사용하기 적합하지 않은 방법이다. 이때 펜윅트리를 사용하면, O(logn)에 해결할 수 있다. 이번 글에서는 펜윅트리에 대해 알아보겠다. 참고로 이번 글에서 n번째라고 하면 배열에서 처럼 0부터 셈을 하는 것이 아닌 일상에서 처럼 1.. 2021. 5. 13. 이전 1 다음
