static_to_dynamic

추가

https://codeforces.com/blog/entry/48417 4번 https://codeforces.com/blog/entry/10725?#comment-160742 이 댓글 설명으로 이해했다. https://koosaga.com/242 1번 https://jeffe.cs.illinois.edu/teaching/datastructures/notes/01-statictodynamic.pdf 보통 Bentley-Saxe라고 부르는것 같다. 아래와 같은 경우 static set에서의 문제를 online incremental버전으로 확장가능하다. Build에 B(N) Query에 Q(N)이 걸리면서 두 분할의 Query 결과를 빠르게(편의상 상수시간으로 하겠다) Merge가능하다면 Build를 B(N)에 Query를 Q(N)log(N)에 풀 수 있다. Aho-corasick에 문자열 추가, 문자열 존재여부 쿼리를 이 방식으로 풀 수 있다. 문자열 존재여부(bool)는 OR로 묶어주면 되니까 풀 수 있는것. 근데 bfs없이 깡DP로 구현한 내 아호코라식은 그냥 add되는듯? https://en.wikipedia.org/wiki/Dynamization 이런 문서가 존재한다. Dynamization of Decomposable search problems이라고 해야할듯? Online incremental convex hull은 이 방법과는 좀 다른것 같고, point in polygon O(logN)으로 위치체크하고, 바깥일시에 접선을 구해서 이분탐색으로 들어갈 자리 구해서 쭉 pop해주면 amortized O(logN)에 되지 않을까? https://codeforces.com/blog/entry/112458

Delete도 방법이 있는것 같다. Stack like undo: persistent붙이면 됨 Queue like undo: https://codeforces.com/blog/entry/83467 PQ like undo: https://codeforces.com/blog/entry/111117 Offline arbitary delete: https://cp-algorithms.com/data_structures/deleting_in_log_n.html (amortized면 불가능) 또 다시, Dynamic convex hull(https://codeforces.com/blog/entry/75929)은 이것과 좀 다른 방법인것 같다.

online: 쿼리를 주어질때마다 처리, offline은 쿼리가 한번에 주어짐 incremental: 하나씩 단계별로 증가시키면서 처리. offline일 수 있는게, 하나씩 추가하다가, 중간에 쿼리결과를 묻고, 다시 추가하고, 이런식으로 한번에 주어지면 offline처리가 가능할수도 있음 dynamic: 추가/삭제 쿼리. 이것도 offline일수 있다. Offline Dynamic Connectivity라던가. persistent: 업데이트시 새로운 버전이 나오지만, 여전히 이전버전의 정보에 접근가능한? 그게 빠르게 업데이트 가능한?