본문 바로가기
반응형

Fenwick Tree

[알고리즘] Lazy Propagation (Segment / Fenwick Tree) [목차] 1. Lazy Propagation이란? 2. Lazy Propagation with Segment Tree 3. Lazy Propagation with Fenwick Tree 4. Lazy Propagation 예시 문제 1. Lazy Propagation이란? 혹시 세그먼트 트리(Segment Tree)와 펜윅 트리(Fenwick Tree)에 대해서 잘 모른다면 이 자료구조들에 대해서 학습한 후, 이 글을 보는 것을 권장한다. 세그먼트 트리나 펜윅 트리는 원소의 update가 있는 경우에 구간합을 빠르게 구해주기 위해서 사용한다. 한 원소의 update는 O(logN)만큼의 시간이 걸리고, 구간합 또한 O(logN)만큼의 시간이 걸리기 때문에 Q를 쿼리의 개수라고 하면 보통 O(QlogN) ..
[BOJ 17353] 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 [문제] www.acmicpc.net/problem/17353 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순 www.acmicpc.net [난이도] - Platinum II (solved.ac 20.12.22 기준) [필요 개념] - Lazy Propagation with Segment Tree - Fenwick Tree 디스크립션은 간단하다. 두 종류의 쿼리가 들어오고, 한 쿼리는 구간 [L, R]에 순서대로 1, 2, ..., R-L+1을 더해준다. 나머지 한 쿼리는 X번째 원소의 값을 출력해준..

티스토리툴바