Persistent segment tree 썸네일형 리스트형 BOJ)13538 XOR 쿼리 문제: icpc.me/13538 5가지 종류의 쿼리를 처리하는 문제이다. 1번 쿼리를 x의 위치에 업데이트 시키는 새로운 세그먼트 트리를 생성한다고 가정하면 persistent segment tree 자료구조를 이용할 수 있다. 고로 1번 쿼리의 경우 트리의 개수 n을 증가시켜주면서 n번째 세그먼트 트리의 x의 위치에 업데이트 시켜준다. 이 방식으로 persistent segment tree를 구축시켜주면 3번 쿼리는 자연스럽게 n=n-k가 된다. 이제 2,4,5의 쿼리를 생각해보자 4번 쿼리의 경우 r번째 세그먼트 트리에서의 0~x의 sum에서 l-1번째 세그먼트 트리에서의 0~x의 sum을 빼줌으로서 처리가능하다. 5번 쿼리의 경우는 r번째 세그먼트 트리가 가지는 값에서 l-1번째 세그먼트 트리가 가.. 더보기 Persistent Segment Tree 먼저 시작하기 전에 .. -오늘 공부한 내용을 제 멍청한 머리가 기억하지 못할까봐 기록하는 개인용 글입니다. -해당 자료구조에 대하여 완벽하게 알고 적는 글이 아니기 때문에 Persistent segment tree를 공부하는 용도로는 좋지 못한 글이 될 확률이 높습니다.-BOJ 11932 문제를 풀기 위해 https://hongjun7.tistory.com/m/64와 http://blog.myungwoo.kr/100 를 많은 부분에서 참고하였습니다. persistent segment tree가 뭔지는 알고있었지만 귀찮아서 공부를 미루다가 오늘 BOJ 11932번을 접하고 도전하게 되었다. persistent segment tree는 가상의 N개의 세그먼트 트리를 O(NlogN)의 공간복잡도로 유지하는 .. 더보기 이전 1 다음