고정 헤더 영역
상세 컨텐츠
본문
펜윅트리는 O(N)에 구할 연산을 O(logN)에 해결할 수 있게 해준다.
( 구간 합 구하기 )
펜윅트리는 "누적합"에 특화되어있는 자료구조이다.
두 가지 연산만 잘 알아두면되는다.
1. update
2. prefix_sum이다.
아래와 같은 도표를 보면 이해가 쉽다!
그림 출처 : https://www.acmicpc.net/blog/view/21
'Python알고리즘' 카테고리의 다른 글
| 백준 11053: 가장 긴 증가하는 부분 수열 (DP / with Python) (0) | 2023.10.04 |
|---|---|
| 백준 10610: 30 (Greedy / with Python) (0) | 2023.10.03 |
| Softeer Level 3: [HSAT 5회 정기 코딩 인증평가 기출] 업무 처리 (구현, 트리 / with Python) (0) | 2023.10.02 |
| Softeer Level 3: [HSAT 5회 정기 코딩 인증평가 기출] 성적 평가 ( 구현 / with Python) (0) | 2023.10.02 |
| Softeer Level3: [HSAT 2회 정기 코딩 인증평가 기출] 사물인식 최소 면적 산출 프로그램 (Back Tracking / with Python) (0) | 2023.10.02 |
