문제 링크
- http://icpc.me/16124
august14님께서 BOJ에서 이벤트를 개최하셨습니다. (이벤트 공지)
다항시간 안에 해결하지 못하는 문제를 적절히 잘 풀어나가는 이벤트로, 재미있어 보이길래 참가했습니다. 이벤트가 2일만에 끝나서 아쉽긴 하지만, 여러가지 시도를 많이 해봤고 오랜만에 재밌게 문제를 풀 수 있었습니다.
3월 16일에 이벤트가 끝나면 올릴 생각이었지만 일찍 끝났길래 지금 올립니다.
이 글에서는 2일동안 제가 이 문제를 풀기 위해 시도한 것들을 정리합니다.
어떤 자료구조가 “persistent하다”라는 것은, 상태의 변화가 생기더라도 과거 상태를 모두 보존하고 있다는 것을 의미합니다.
Persistent Segment Tree(PST)는 세그먼트 트리의 갱신 과정을 모두 저장하고 있는 자료구조입니다.
평범하게 세그먼트 트리를 구현하면 공간복잡도는 O(N)입니다. 이런 문제를 생각해봅시다.
0으로 초기화된 길이 N인 수열이 있을 때, 수 하나를 변경하는 쿼리와 구간의 합을 구하는 쿼리가 총 Q개 주어집니다. 이때 N ≤ 1,000,000,000이고 Q ≤ 100,000이고, 쿼리가 들어올 때마다 해당 쿼리에 대한 답을 내야 합니다.(온라인 쿼리)