Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
[Fenwick Tree Lazy propagation] - 펜윅 트리에 Lazy propagation 적용하기
Fenwick Tree 펜윅 트리 기존의 펜윅 트리에 대해서는 깔끔하게 설명하신 백준님의 게시글을 보고 오자. 펜윅 트리 (바이너리 인덱스 트리) - BaekJoon 펜윅 트리는 세그먼트 트리와는 다르게 부분 합(첫 원소에서 부터 i개의 값)을 계산하는데 특화되었다.(이 특징이 가장 중요합니다!!!) 백준 님이 설명한 펜윅 트리에서는 점 업데이트(Point Update)와 구간 쿼리(Range query)가 가능하다. 따라서 [L,R]구간의 구간합은 [1,R]까지의 합(pSum(R) ) - [1,L-1]까지의 합( pSum(L-1) )으로 구할 수 있다. 하지만 원소의 업데이트는 한 개씩만 진행할 수 있다. 따라서 백준 - 수열과 쿼리 21(16975) 문제와 같은 구간의 업데이트를 요구하는 문제는 일일..
알고리즘 공부/알고리즘 기법
2021. 2. 27. 15:16