data_structure

3 posts

스턴 브로콧 트리(Stern Brocot tree)

먼저, 모든 양의 분수를 나열하는 방법에 대해 알아봅시다. 다음 두 분수가 있습니다. [\dfrac{0}{1}, \dfrac{1}{0}] 두 번째는 엄밀히 분수는 아니지만, 무한대를 나타내는 기약분수로 해석합시다. 매 반복마다, 모든 인접한 분수 $\dfrac{a}{b}$ 와 $\dfrac{c}{d}$ 사이에 mediant인 $\dfrac{a+c...

Segment Tree (+ Lazy Propagation) 코드 최적화

원문 : https://codeforces.com/blog/entry/18051 Segment tree with single elment modifications Segment tree는 한 배열에서 몇 번의 변경이나 연속된 부분에 대한 query들을 처리할 때 사용한다. 첫번째 예로 다음 두 명령어를 생각해두자.  배열에 있는 한...

Range Queries와 Modifications over Array의 Non-recursive 구현

양의 정수 $N$이 2의 지수라고 하자. 길이가 $N$인 배열 $a$의 각 원소를 $a_i$라고 하자$(i \in [0, N-1])$. 어떤 원소 $a_i$를 수정하는 규칙이 있을 때, 이것을 $a_x$와 $a_y$ 사이 모든 원소들에 적용시킨다고 생각하자. 이것을 Range modification이라고 부를 것이다.  결합법칙(Associative...