전체태그 보기

#펜윅트리 (2개의 포스트)

doontagi
문제 풀이 이 문제에는 세 가지 풀이가 있다. 1. 펜윅 트리 활용 펜윅 트리는 구간합을 간단하고 빠르게 구할 수 있는 자료 구조이다. 구간합을 활용해서 이 문제를 푸는 방법은 펜윅 트리의 크기를 문제에서 주어진 정수 범위로 하는 것이다. 모든 정수에 대해여 펜윅 트리를 만들고, 배열의 첫 원소부터 하나씩 갱신하면서 그 원소보다 큰 원소의 개수를...
doontagi

펜윅트리

2019년 7월 16일0개의 댓글
펜윅트리 배열의 구간합을 구하는 데는, 구간 트리를 활용할 수 도 있지만 그 구현이 복잡해 조금 더 단순한 형태인 펜윅트리를 사용하는 것이 더 좋다. 펜윅트리란 배열의 첫 몇 개의 원소인 부분합을 활용하면 구간합도 빠르게 계산할 수 있다는 원리에서 출발한 구조이다. image.png 펜윅트리의 구현 펜윅트리를 실제로 구현하기 위해서는 이진수를...