Fenwick Tree (2) 썸네일형 리스트형 161. 2D Segment Tree & 2D Fenwick Tree $2$D 세그먼트 트리($2$D Segment Tree)는 세그먼트 트리를 $2$차원으로 구성한 것이다. 즉 $1$차원 세그먼트 트리들이 여러 개 존재하고 여기서 같은 위치에 있는 노드들로 구성된 세그먼트 트리들이 추가로 존재하는 방식이다. 다음과 같이 $4 \times 4$ 크기의 테이블이 존재할 때 $2$차원 세그먼트 트리를 어떻게 구성하는지 알아보자.ABCDEFGHIJKLMNOP$1$차원 세그먼트 트리를 구현할 때 $1$차원 배열을 선언했다. 비슷하게 $2$차원 세그먼트 트리를 $2$차원 배열로 구현할 것이다. 그러면 첫 번째 인덱스를 행, 두 번째 인덱스를 열에 대응해서 각 노드가 어느 범위의 데이터를 저장할지 결정할 수 있다.더보기첫 번째 인덱스로 다음과 같이 행 범위를 지정한다.$a[1][]$.. 159. Fenwick Tree 세그먼트 트리의 변형 버전인 펜윅 트리(Fenwick Tree)에 대해 알아본다. 펜윅 트리는 세그먼트 트리의 구조를 응용하여 원소들의 값이 변할 수 있을 때 누적합을 빠르게 구할 수 있게 하는 자료 구조이다. 먼저 합 세그먼트 트리에서 누적합을 구할 때 어떤 노드들이 사용되는지 확인해 보자. 합 세그먼트 트리를 설명할 때 노드들에 위와 같이 번호를 매기는 것이 일반적이라고 했다. 여기서 앞쪽 $k$개 원소의 누적합을 구할 때 합에 포함되는 노드들의 번호를 나열하면 다음과 같다. $k=1$인 경우: $8$ $k=2$인 경우: $4$ $k=3$인 경우: $4$, $10$ $k=4$인 경우: $2$ $k=5$인 경우: $2$, $12$ $k=6$인 경우: $2$, $6$ $k=7$인 경우: $2$, $6$,.. 이전 1 다음
