Table of Contents 개요 트리 펼치기 Mo's algorithm 의 적용 문제 1. 개요 https://www.acmicpc.net/problem/13518 위 문제와 같이 트리에서의 쿼리를 처리할 때, 쿼리의 처리 순서를 마음대로 조작할 수 있다면, DFS로 트리 펼치기 + Mo's algorithm 의 조합으로 시간 복잡도 O( (N+Q) * sqrt N * f(x) ) 을 맞춰 줄 수 있는 경우들이 있습니다. ( * f(x) = 모스 알고리즘에서 노드의 추가 / 삭제 시 필요한 시간복잡도 ) 2. 트리 펼치기 트리에서 DFS를 돌면서, 각각의 DFS 함수가 '시작 했을 때', 그리고 '끝날 때' 해당하는 노드를 배열에 추가해서 트리를 펼치는 스킬입니다. 아래 예시를 통해 알아보겠습니다...
Table of Contents 개요 1D sparse table 쿼리를 O(1)으로 처리하기 2D sparse table 문제 1. 개요 스파스 테이블은 배열 Array[1...N], 함수 Function, 범위 [L, R] 이 주어질 때 Function(Array[L], Array[L+1], ..., Array[R]) 계산을 빠르게 하기 위한 자료구조입니다. 간단하게 예를 들면, 'A[3] ~ A[7] 사이의 최소값을 구하라.'같은 식입니다. 여기에서 함수는 최소값 찾기, L = 3, R = 7이 되겠지요. 스파스 테이블은 아래의 두 조건이 성립할 때 사용할 수 있습니다. 조건 1) Array에 저장된 값이 변하지 않야야 한다. 조건 2) Function은 결합 법칙이 성립해야 한다. (즉, F(a,..
Table of Contents 개요 쿼리 처리 쿼리 정렬 문제 1. 개요 https://www.acmicpc.net/problem/13547 먼저 위의 문제를 읽어주시길 바랍니다. 범위 쿼리를 처리하는 상황에서 가끔 이런 상황들이 있습니다. 배열 Array[1...N], 함수 Function, 범위 [L, R] 이 주어질 때 Function(Array[L], Array[L+1], ..., Array[R]) 계산하는데, 배열에 저장된 값을 고치는 update 연산은 없는 상황입니다. 위의 문제가 그 예시이지요. 이런 상황을 만나면 Segment tree 나 Sparse table 로 접근하는 경우가 많습니다. 하지만 이 두 자료구조를 활용한 접근은 대체로, 온라인 처리가 아닌 배치 처리가 가능하다는 점을..