Persistent Segment Tree 구현 메모

난 이 글의 마지막 부분을 보고 퍼시스턴트 세그먼트 트리를 익혔다.

 

일단 내 나름대로 퍼시스턴트 트리를 떠올려 보았다.

 

과거 기록을 모두 가지고 있는 트리.

 

때마침 수쿼22가 그런 컨셉의 문제였고, 나는 스스로 이 문제를 풀어보았다.

 

어떤 원소를 업데이트할 때 그 원소로 인해 업데이트 되는 세그먼트 트리의 노드는 최대 O(log N)개다. 그럼 각 쿼리마다 log N개의 '기록'만 추가된다는 것. 세그먼트 트리의 각 노드를 '벡터'로 만들어서 k번째 쿼리에는 이 값을 가지고 있었다는 사실을 저장하면 되지 않을까? 별도로 인덱스 배열을 만들어서 나는 'x번째 쿼리'때 이 값으로 변경되었어요~를 저장하면 추후 이분탐색으로 2번 쿼리를 처리할 수 있다.

 

구현 성공!

업뎃 쿼리는 O(log N), k번째 업뎃 직후 구간합 구하기 쿼리는 O(log^2 N)에 동작한다.

포인터로 구현 안해서 훨씬 깔끔하게 느껴진다.

boj.kr/febc04bbda5f456cbfe13c4bfbb8804e

Seg 구조체 내용만 보면 된다

 

여담으로 이 문제에서 난 당연히 PST를 구현해야 한다고 생각했지만... 오프라인 쿼리로 만들어버리는 순간 끝난다. 항상 더 쉬운 방법을 먼저 찾자!

 

ㅋㅋㅋ 난 내가 퍼시스턴트 트리를 구현했다고 생각했지만

제대로 된 퍼시스턴트 트리는 O(log N)에 동작했다. 내건 log^2N

동적할당 계속하는 방법도 있고 인덱스 추가하는 방법도 있던데 난 인덱스 추가하는게 훨씬 깔끔하다고 생각한다. 동적할당 하는건 구조체 만들어야 돼서 별로.

boj.kr/a8442502fe8541d6bf90fd38a26248b4

 

K번째 수 

boj.kr/230b0a2dfd0645a6872f835c04af559b

 

핵심 아이디어는 i번째 수를 i번째 업데이트라 보는 것,

a~b에서 k번째 수 찾기를

a~b번째 업데이트가 일어난 세그 트리에서 k번째 수 찾기로 변환한다.

전구간에서 k번째 수 찾기는 O(log N)에 처리하는 방법이 널리 알려져 있다. (루트에서 타고 내려가기)

 

인상깊었던 건 내 log^2 N 머지소트 트리 풀이와 실행시간이 정확히 같았다는 것. :V

 

+ 퍼시스턴트 트리가 결국 동적 세그 트리 기반이기 때문에 좌표압축을 하지 않아도 코드가 돌아간다!

단, 배열로 세그 트리를 구현했을 경우 메모리 사용량 계산이 귀찮다.

메모리 계산 방법

배열 길이 N:  4*N + Q log N

원소 범위 길이 R: Q log R

k번째 수 같은 경우 R이 20억이기 때문에 log R이 60이다.

Q가 5000이므로 인덱스 범위를 0~350만 정도로 보는게 안전하다.

root[0] = 1로 잡으면 편해짐. 앞으로도 그냥 root[0]을 1로 잡아야겠다. 

아님. 0이 훨씬 편하다 ㅋㅋ

root[0] = 0인게 제일 이상적. 

1번째 업데이트 후부터 root[1] >= 1 이렇게 되어야 함.

구현: boj.kr/3662205646f0457ba6ae56c5a97b06e0

쿼리가 일반적인 구간합 쿼리라면

return (L[id]?Query(L[id]):0) + (R[id]?Query(R[id]):0);

이런 식으로 하면 된다. 이러면 시간복잡도가 보장됨.

 

Egg.

이차원 구간 쿼리 문제다.

옜날에 정말 쩔쩔맸던 문젠데 지금 PST로 다시 보니 감회가 새롭다.

vector로 하는 코드를 짰는데 훨씬 범용적이다.

당분간 PST는 이 코드로 짠다.

boj.kr/2f586c797dc9406b8d9a22ae153d92e3