펜윅트리1 [PS를 위한 자료구조 8강] 펜윅 트리의 개념과 구현 (Orderstatic Tree) PS를 위한 자료구조 1-8강 # 펜윅 트리의 개념과 구현 # 에 대해 알아보겠습니다. 지금까지 세그먼트 트리에 대해 배웠고 잘 따라온 여러분들에게 감사할 따름입니다. 이번 시간에 배워볼 자료구조는 "펜윅 트리"입니다. 펜윅 트리는 세그먼트 트리의 일종으로, 비재귀 세그먼트 트리에 분류할 수 있습니다. 역시 비재귀 세그먼트 트리답게 이해하는게 쉽지는 않지만, 구현 난이도는 비재귀 세그먼트 트리보다도 쉽습니다. 아래의 세그먼트 트리의 구조를 다시 봅시다. 그런데 이 중에 필요없는 구간이 있지 않을까요? 생각해보면 [1 8] 노드와 [1 4] 노드가 있으면 [5 8] 노드는 필요없는게 아닐까요? [1 8] 노드의 값에서 [1 4] 노드의 값을 빼준다면 [5 8] 노드의 값을 구할 수 있을 것입.. 2022. 3. 24. 이전 1 다음