Euler tour technique 이란 트리를 전위 탐색(부모 -> 자식)으로 넘버링 해서 트리를 관리하는 테크닉이다. 이러한 방식으로 트리를 관리하면 트리에서 임이의 서브트리에 대한 쿼리를 쉽게 처리할 수 있다. 트리에 전위 탐색으로 넘버링을 하고, 임의의 노드에 대해 생각해보다. 이 노드를 루트로 하는 서브트리 내에 속하는 모든 정점들은 인접하고 연속하게 넘버링이 되어있다는 것을 알 수 있다. 다음의 사진을 보자. (검정 : node number, 파랑 : 전위 탐색으로 넘버링 된 수) 여기서 2를 루트로 하는 서브트리 내의 모든 정점들에 대해 넘버링 된 수들을 나열해 보면 2, 3, 4, 5, 6 으로 연속한 것을 알 수 있다. 이러한 특성 때문에 오일러 투어 테크닉과 세그먼트 트리 같은 자료구..

Introduction monotone queue 란 deque 의 상태를 증가하거나 감소하도록 유지시켜 수열의 특정 구간에서 최대 또는 최소를 찾는 기법이다. 다음의 문제를 보자. http://boj.kr/11003 우리는 길이가 L 인 연속한 모든 구간들에 대해서 최솟값을 찾아줘야 한다. 물론 가장 naive한 방법으로는 세그먼트 트리를 이용한 방법이 있겠지만, monotone queue 테크닉을 사용하면 O(n)이라는 세그보다 (O(n log n)) 훨씬 빠른 속도로 문제를 풀 수 있다. 최솟값을 구하는 경우 i와 j는 i ar..