Fenwick Tree 펜윅 트리 기존의 펜윅 트리에 대해서는 깔끔하게 설명하신 백준님의 게시글을 보고 오자. 펜윅 트리 (바이너리 인덱스 트리) - BaekJoon 펜윅 트리는 세그먼트 트리와는 다르게 부분 합(첫 원소에서 부터 i개의 값)을 계산하는데 특화되었다.(이 특징이 가장 중요합니다!!!) 백준 님이 설명한 펜윅 트리에서는 점 업데이트(Point Update)와 구간 쿼리(Range query)가 가능하다. 따라서 [L,R]구간의 구간합은 [1,R]까지의 합(pSum(R) ) - [1,L-1]까지의 합( pSum(L-1) )으로 구할 수 있다. 하지만 원소의 업데이트는 한 개씩만 진행할 수 있다. 따라서 백준 - 수열과 쿼리 21(16975) 문제와 같은 구간의 업데이트를 요구하는 문제는 일일..

문제 https://www.algospot.com/judge/problem/read/MEASURETIME algospot.com :: MEASURETIME 삽입 정렬 시간 재기 문제 정보 문제 유명한 정렬 알고리즘인 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해 나가는 식으로 동작합니다. 주어진 정수 배열 A를 정렬하는 www.algospot.com 풀이 종만북 난이도: 중 세그먼트 트리와 같은 기능을 하지만 비트 연산을 이용해 좀 더 간단히 구현이 가능한 펜윅 트리(Fenwick Tree) 혹은 이진 인덱스 트리(binary indexed tree)로 해결하는 문제이다. 펜윅 트리는 세그먼트 트리와는 다르게 부분 합(첫 원소에서 부터 i개의 값)을 계산하는 데 특화되어 있다. 만..