서론

어떤 자료구조가 “persistent하다”라는 것은, 상태의 변화가 생기더라도 과거 상태를 모두 보존하고 있다는 것을 의미합니다.
Persistent Segment Tree(PST)는 세그먼트 트리의 갱신 과정을 모두 저장하고 있는 자료구조입니다.

서론

평범하게 세그먼트 트리를 구현하면 공간복잡도는 O(N)입니다. 이런 문제를 생각해봅시다.
0으로 초기화된 길이 N인 수열이 있을 때, 수 하나를 변경하는 쿼리와 구간의 합을 구하는 쿼리가 총 Q개 주어집니다. 이때 N ≤ 1,000,000,000이고 Q ≤ 100,000이고, 쿼리가 들어올 때마다 해당 쿼리에 대한 답을 내야 합니다.(온라인 쿼리)

문제 링크

• http://icpc.me/13519

문제 링크

• http://icpc.me/13517

문제 링크

• http://icpc.me/13516

문제 링크

• http://icpc.me/13515

서론

세그먼트 트리는 분할 정복을 메모이제이션하는 자료구조라고 할 수 있고, 이런 성질을 통해 다양한 문제를 해결할 수 있습니다.
이 글에서는 분할 정복을 이용하는 합병 정렬(Merge Sort)을 메모이제이션하는 Merge Sort Tree와 이것을 이용해 해결할 수 있는 문제들을 다룹니다.

문제 링크

• http://icpc.me/10839

서론

어떤 문제에서 답이 단조성을 가질 때는 binary search 등을 이용한 parametric search로 빠르게 답을 구할 수 있습니다.
병렬 이분 탐색(Parallel Binary Search, PBS)는 parametric search의 각 결정 문제를 스위핑 하듯이 풀 수 있는 몇몇 경우에 적용할 수 있는 기법입니다. 말로 설명하기 힘드니 문제와 함께 소개하겠습니다.

문제 링크

• http://icpc.me/16000