펜윅트리 시간복잡도 (1) 썸네일형 리스트형 펜윅트리(Fenwick Tree) 자료구조 펜윅트리(Fenwick Tree) 펜윅트리를 공부하기 전에 우선 세그먼트 트리에 대한 이해와 그 필요성에 대해 알아야한다. 세그먼트 트리는 구간의 정보를 빠르게 가져올때 사용한다. 기존 세그먼트 트리를 설명하면서 크기 N의 배열에 대해 필요한 트리의 사이즈는 2^(트리의 높이+1)이라고 잠시 짚고 넘어갔었다. 트리의 높이는 밑이 2인 logN이므로 트리를 구성하기 위해선 대충 4N정도의 크기가 필요하다. 또한 세그먼트 트리는 구현도 복잡하다..ㅎㅎ 펜윅트리은 이 문제를 해결할 수 있다. 결론부터 말하자면 크기 N의 배열에 대해 N만큼의 크기가 트리구성에 필요하고 구현또한 매우매우 간단하다. (이해만 한다면..) 펜윅트리를 이해하기 위해서는 또 한가지를 알아야 한다. 바로 비트마스크연산이다. 비트마스킹을 .. 이전 1 다음
