[알고리즘] Splay Tree를 사용해서 해결할 수 있는 유형

Splay Tree 를 사용하면 백준 태그에 Splay Tree가 붙은 문제 외에도 많은 문제를 해결할 수 있다. 여기에서 해결할 수 있는 문제들을 유형별로 정리하고 풀이를 간단하게 소개한다. 문제의 순서는 난이도 순이 아닐 수 있다.

 

기본 연산 유형

Splay Tree는 값의 insert, delete, find연산을 지원한다. 이를 사용하여 해결할 수 있는 문제들이다.

11723. 집합

원래는 비트마스킹 연습하라고 메모리가 적게 세팅된 문제이지만 Splay Tree를 잘 구현하면 제한 안에 통과할 수 있다. Splay Tree를 연습하기 좋다. insert와 delete, find같은 기본 연산만으로 해결할 수 있다.

1269. 대칭 차집합

11723을 해결하며 toggle을 잘 구현했다면 toggle만으로 해결할 수 있다.

1822. 차집합

Splay Tree를 구성하여 $A$의 모든 원소를 insert하고 $B$의 모든 원소를 erase한 후 남은 원소들을 출력하면 된다.

8834. Kolejka

이전에 들어온 사람 인덱스를 기억하여 해당 인덱스 뒤에 insert하면 된다.

31590. Candy Compress

9548. 무제

쿼리에서 소개하는대로 삽입하라는 곳에 삽입하고 제거하라는 곳에 제거하면 된다. 구간 삽입/제거이지만 naive하게 해도 된다.

16586. Linked List

최종 결과만 출력하라고 했다면 문제 제목대로 Linked List를 사용하여 해결하면 되지만 거리까지 구하라고 해서 Splay Tree를 사용해야한다. 그냥 $a$가 있는 위치의 노드를 erase하고 $b$의 오른쪽에 붙여준 후 두 인덱스의 차이를 구해주면 된다. 인덱스는 find_kth한 후 왼쪽 서브트리의 크기와 같다.

Data Structure 유형

10828. 스택

10845. 큐

10866. 덱

1927. 최소 힙

7662. 이중 우선순위 큐

Splay Tree는 스택, 큐, 덱같은 선형 자료구조는 물론, 우선순위 큐, 이중 우선순위 큐같은 일부 2차원 자료구조도 해결할 수 있다.

Segment Tree 유형

Splay Tree의 구간을 한 Node로 모으면 구간 쿼리를 처리할 수 있다.

2042. 구간 합 구하기

2357. 최솟값과 최댓값

11505. 구간 곱 구하기

Segment Tree를 처음 배울 때 접하게 되는 구간 쿼리 유형이다. 단일 업데이트이므로 find_kth를 사용하여 루트로 올린 후 업데이트하고 Node를 모아 구간 쿼리를 처리한다.

10999. 구간 합 구하기 2

14245. XOR

1395. 스위치

Lazy propagation을 처음 배울 때 접하게 되는 문제들이다. 구간 업데이트이므로 Node를 먼저 모아 lazy를 setting하고 lazy가 있는 노드들을 rotate할때마다 push하여 업데이트하고 Node를 모아 구간 쿼리를 처리한다.

 

BBST 유형

Splay Tree도 PBDS와 마찬가지로 특정 값을 가진 원소의 인덱스 찾기, 특정 위치에 있는 원소의 값 찾기 연산을 각각 지원하므로 PBDS로 해결할 수 있는 문제를 해결할 수 있다. Segment Tree로도 해결할 수 있다.

1849. 순열

10090. Counting Inversions

BBST의 특성을 가장 잘 사용할 수 있는 Inversion Counting 유형이다. Splay Tree를 BBST로 사용하면 현재 노드의 오른쪽 서브트리에 현재 노드 값보다 큰 값들만 모여있기 때문에 앞에서부터 Splay Tree에 insert하면서 오른쪽 서브트리의 개수를 더해주면 된다.

1168. 요세푸스 문제 2

30853. Black Box

31865. 수열 만들기

요세푸스 유형이다. 다음 제거 대상인 인덱스를 찾는 것은 쉽게 구할 수 있다. 해당 인덱스를 삭제하면 되기 때문에 Splay Tree를 구성한 후 erase만으로 해결할 수 있다.

Small to Large trick 유형

small to large는 집합을 합칠 때 작은 것을 큰 것에 합쳐서 시간복잡도의 이득을 보는 트릭이다. Splay Tree는 두 집합을 합칠 때 포인터 연산을 하기 때문에 상수시간에 합칠 수 있다. 작은 것에 큰 것을 합쳐도 시간복잡도가 똑같다!

28277. 뭉쳐야 산다

두 Splay Tree를 합치는 연산을 구현하여 1번 쿼리를 해결할 수 있다. 이는 위에서 언급한 것 처럼 트리의 루트를 다른 트리의 왼쪽 끝이나 오른쪽 끝에 붙여서 구현할 수 있다. 2번 쿼리는 트리의 크기를 출력하면 된다.

reverse, shift 유형

동적으로 변화하는 Splay Tree의 특성을 사용하여 구간 뒤집기와 shift를 하여 문제를 해결할 수 있다.

16994. 로프와 쿼리

14131. Okret

13159. 배열

문제에서 소개하는대로 정직하게 reverse와 shift를 구현하여 해결하면 된다. 난이도 차이가 왜 있는지는 모르겠다. 배열 문제는 구간 쿼리나 점쿼리가 포함되어 있지만 위의 문제들을 해결했다면 어렵지 않게 해결할 수 있는 문제

19589. 카드 셔플

1, 2는 단순 shift쿼리이고 3번은 제한이 1000이기때문에 dfs를 사용해서 해결해도 시간이 넉넉해서 통과된다. 

 

구간에 등차수열을 업데이트하는 유형

기본 lazy propagation은 구간에 같은 값을 더하거나 대입하지만 등차수열로 업데이트하라는 문제가 있다. lazy값을 push할 때 초항과 공차를 잘 push하면 된다. 초항이 $a$이고 공차가 $d$인 등차수열을 구간에 업데이트하려면 아래 그림과같이 하면 된다.

구간 합을 기록하려면 등차수열 합 공식인 $S = n \frac{a + l}{2}$를 더해주면 된다. $a$는 구간 초항, $l$은 구간 마지막 항

17353. 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

20305. 피보나치와 수열과 쿼리

위와 같이 업데이트를 잘 했다면 이 두 문제를 해결할 수 있다. 20305는 값을 더할 때 값에 대응하는 피보나치 수를 더해주면 된다.

26087. 피보나치와 마지막 수열과 쿼리

정해는 20305와 많이 다르지만 Splay Tree를 사용하면 한 줄만 바꿔서 통과할 수 있다. 20305번에서 값을 업데이트할 때 한 덧셈연산을 대입연산으로 바꾸기만하면 해결할 수 있다.

2844. 자료 구조

1, 3, 4번쿼리는 위에서 많이 나온 유형이고 2번은 등차수열을 업데이트하라는 쿼리이므로 위 문제들과 유사하게 해결하면 된다.

연속 최대 부분합 유형

연속 최대 부분합은 구간의 왼쪽 최대 부분합, 오른쪽 최대 부분합, 두 구간을 포함하는 최대 부분합을 조합하여 해결한다. 금광세그라고도 알려져있다.

16993. 연속합과 쿼리

17346. Maintaining a Sequence

Splay Tree에서 위 방법으로 구간 최대 부분합을 구할 수 있다면 위 문제를 해결할 수 있다.

17607. 수열과 쿼리 31

1번은 단순 reverse쿼리이다. 2번 쿼리를 해결하기 위해 연속 최대 부분합에서 조건을 단순 합이 아닌 1의 개수를 세는 것으로 바꾸면 해결할 수 있다.

---

Splay Tree로 해결할 수 있는 고난도의 문제가 많아서 제대로 이해했다면 다이아까지는 문제 없이 달성할 수 있을 것이다...