PS를 하면서 Persistent라는 단어가 붙는 자료구조는 Persistent Segment Tree 외에는 보기 힘들지만, 사실 Persistent라는 prefix는 꽤나 일반적인 의미를 지닌다. 어떤 자료구조를 계속 업데이트하면서도 이전 버전에 접근할 수 있을 때 그 자료구조를 'Persistent하다'고 한다. 조금 더 세부적으로 분류하면, 이전의 모든 버전에 접근, 수정이 가능하다면 Fully persistent, 이전의 모든 버전에 접근이 가능하지만 최종 상태를 제외하면 모두 read - only라면 Partially persistent 혹은 Confluently persistent라고 한다. 분류는 거창하지만 구현이 그렇게 난해한 건 아니다. 일반적인 방법론은 Fat node, Path co..

아직 공부중인 자료구조 / 알고리즘들이다.세상에 똑똑한 사람이 너무 많아.. 1. DP tricks 1.1. Alien Trick (Wang Qing-Shi Binary Search) 구사과 블로그imeimi 블로그원문을 구할 수 있는 곳 (중국어) IOI 2016 AliensNAIPC 2017 Blazing new trails 1.2. dynamic CHT (without pointer) 일명 성적CHT. 본지가 언제인데 아직도 못 짜냐 ㅡㅡ 1.3 Li-Chao tree Doc2 csacademy 연습문제 1.4. Knuth Optimization with rigorous proof 2. Offline Dynamic Tricks 2.1. Offline Dynamic Connectivity 2.2. D..