구간 합 구하기 3 (1) 썸네일형 리스트형 2차원 펜윅트리 이해하기(2-dimentional Fenwick Tree) 펜윅트리는 비트연산을 통해 빠른 시간에 구간합을 구하는 배열 형태의 트리이다. 이 글에서는 2차원 펜윅트리만을 설명하고 있다. 1차원 펜윅트리에 대한 이해가 필요하면 블로그 내 펜윅트리 글(https://uldada.tistory.com/5)을 참고하자. 2차원 펜윅트리 우선 2차원 펜윅트리의 Update와 Sum 함수를 보자. 코드를 보면 x축(여기에선 열을 의미)으로 펜윅트리가 동작하며, 그 안에 while문을 통해 y축(행을 의미)으로 펜윅트리가 동작한다. 일단 update를 통해 초기화(입력받은 배열을 통해 펜윅트리 채워나가기)를 진행해 보자 초기화는 update 함수를 통해 진행된다.(1차원 펜윅트리와 동일한 방식) 입력받은 배열은 아래와 같다. 1 2 3 4 5 6 7 8 9 10 11 12 .. 이전 1 다음
