서론

평범하게 세그먼트 트리를 구현하면 공간복잡도는 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

문제 링크

• http://icpc.me/17731 (일본어 원문)
• https://oj.uz/problem/view/JOI14_historical (한국어 번역)