펜윅트리 (1) 썸네일형 리스트형 펜윅 트리(Fenwick tree, Binary Indexed Tree) 변경되는 데이터 속에서 구간 합을 구하거나 최대/최소, 구간 곱 등을 구할 때 세그먼트 트리(링크)를 사용하였다. 하지만 세그먼트 트리는 N개의 배열이 있을 때 4*N개의 공간을 할당해야했기 때문에 많은 메모리를 필요로 하였다. 세그먼트 트리와 비슷한 역할을 하면서 N개의 공간을 사용하는 자료 구조가 있다면..? 그렇다. 그것이 바로 펜윅 트리이다. 펜윅 트리 펜윅 트리 또는 Binary Indexed Tree(BIT)라고 부른다. Binary Indexed Tree라는 이름에서 알 수 있듯이 인덱스로 이진수를 사용한다. 이것이 무슨 말이냐 하면, (그림 출처) n = 16인 위와 같은 배열이 있다고 가정하면, 각각의 수가 2진수로 나타냈을 때 어디에 마지막 1이 있는지를 알아야 한다. 1 = 0001(.. 이전 1 다음
