트라이 (Trie) 우리가 여러 개의 문자열을 가지고 있을 때, 어떤 문자열이 그 문자열 중 하나인지 알아내는 방법을 생각해보자. 단순하게 일일히 비교하는 방법이 있겠지만, 이러한 방법은 매우 비효율적이다. 최대 길이가 M인 문자열 N개의 집합에서 마찬가지로 최대 길이가 M인 문자열이 그 문자열의 집합에 포함되는지를 일일히 확인하면 최악의 경우 O(NM)의 비교 횟수가 필요하다. 이때, 문자열을 효율적으로 저장하고 탐색할 수 있는 자료구조가 트라이(Trie)다. Prefix tree, Digital search tree, Retrieval tree라고 부르기도 한다. 프레드킨이 Retrieval tree에서 "Trie"라는 이름을 붙였다. 트라이는 특정 문자열을 찾는 작업을 O(N)만에 해결할 수 있다...

Segment Tree 배열 A[1], ..., A[N]이 있을 때, 아래 문제를 생각해보자. [문제 1] 순서쌍 (i, j)에 대하여 A[i], ... ,A[j] 중 최솟값을 찾는 경우를 생각해보자. A[i]부터 A[j]까지 순회하면서 찾는 것이 가장 단순한 방법일 것이다. 이 경우 시간 복잡도는 O(N)이 된다. 그러나 이러한 연산이 Q개 주어지고 N과 Q의 범위가 1부터 10만이라면, 시간 복잡도가 O(NQ)이므로 오랜 시간이 걸릴 것이다. [문제 2] 구간 [l, r] (l ≤ r)이 주어진다. (1) A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력한 뒤, (2) i번째 수를 v로 바꾼다. 이 과정을 M번 반복한다. (1)번 과정은 O(N), (2)번 과정은 O(1)..