Implicit Treap: 배열 인덱스 기반 Treap

Implicit Treap, 묵시적 트립

정의

Implicit Treap 은 Treap 에서 키 대신 서브트리 크기 (위치) 로 인덱싱하는 변형입니다. 배열의 삽입/삭제/이동/구간 반전 등을 O(log N) 에 지원합니다.

특징

• split(t, k): k 번째까지 왼쪽, 나머지 오른쪽
• merge(a, b): 두 배열 이어붙임
• reverse(l, r): 구간 반전 (lazy propagation)
• insert/erase at position: O(log N)

응용

• 편집기 (rope): 임의 위치 삽입/삭제
• 구간 회전, 뒤집기 문제
• LIS 유사 dynamic 문제

참고

• Treap
• BST