콘텐츠로 이동

트립 (데카르트 트리)

트립은 이진 트리와 이진 힙을 결합한 자료 구조입니다(그래서 이름이 tree + heap $\Rightarrow$ Treap입니다).

더 구체적으로 말하면, 트립은 쌍 $(X, Y)$를 이진 트리에 저장하되 $X$에 대해서는 이진 탐색 트리이고 $Y$에 대해서는 이진 힙이 되도록 저장하는 자료 구조입니다. 트리의 어떤 노드가 값 $(X_0, Y_0)$을 가지고 있다면, 왼쪽 서브트리의 모든 노드는 $X \leq X_0$을 만족하고, 오른쪽 서브트리의 모든 노드는 $X_0 \leq X$를 만족하며, 왼쪽과 오른쪽 서브트리의 모든 노드는 $Y \leq Y_0$을 만족합니다.

트립은 데카르트 평면에 쉽게 나타낼 수 있기 때문에 "데카르트 트리"라고도 자주 불립니다:

트립은 1989년 Raimund Siedel과 Cecilia Aragon이 제안했습니다.

이러한 데이터 구성 방식의 장점

이러한 구현에서 $X$ 값은 키(동시에 트립에 저장되는 값)이며, $Y$ 값은 우선순위라고 부릅니다. 우선순위가 없다면 트립은 $X$에 대한 일반적인 이진 탐색 트리가 되며, 하나의 $X$ 값 집합이 서로 다른 많은 트리에 대응될 수 있습니다. 그중 일부는 (예를 들어 연결 리스트 형태로) 퇴화되어 있어 매우 느립니다(주요 연산이 $O(N)$ 복잡도를 가지게 됩니다).

한편 우선순위는 (서로 다를 때) 만들어질 트리를 유일하게 결정할 수 있게 해 주며(물론 트리는 값을 추가하는 순서와 무관합니다), 이는 해당 정리를 이용해 증명할 수 있습니다. 당연히 우선순위를 무작위로 선택하면 평균적으로 퇴화되지 않은 트리를 얻게 되며, 이를 통해 주요 연산의 복잡도가 $O(\log N)$으로 보장됩니다. 그래서 이 자료 구조는 무작위 이진 탐색 트리라고도 부릅니다.

연산

트립은 다음 연산을 제공합니다:

  • Insert (X,Y): $O(\log N)$.
    트리에 새 노드를 추가합니다. 한 가지 변형으로는 $X$만 전달하고 연산 내부에서 $Y$를 무작위로 생성하는 방법이 있습니다.
  • Search (X): $O(\log N)$.
    지정한 키 값 $X$를 가진 노드를 찾습니다. 구현은 일반적인 이진 탐색 트리와 동일합니다.
  • Erase (X): $O(\log N)$.
    지정한 키 값 $X$를 가진 노드를 찾아 트리에서 제거합니다.
  • Build ($X_1$, ..., $X_N$): $O(N)$.
    값의 목록으로부터 트리를 만듭니다. 이는 선형 시간에 수행할 수 있습니다($X_1, ..., X_N$이 정렬되어 있다고 가정합니다).
  • Union ($T_1$, $T_2$): $O(M \log (N/M))$.
    모든 원소가 서로 다르다고 가정하고 두 트리를 병합합니다. 병합 과정에서 중복 원소를 제거해야 하는 경우에도 같은 복잡도를 달성할 수 있습니다.
  • Intersect ($T_1$, $T_2$): $O(M \log (N/M))$.
    두 트리의 교집합(즉, 공통 원소)을 구합니다. 여기서는 이 연산의 구현을 다루지 않습니다.

또한 트립은 이진 탐색 트리이므로 $K$번째로 큰 원소 찾기나 원소의 인덱스 찾기와 같은 다른 연산도 구현할 수 있습니다.

구현 설명

구현 측면에서 각 노드는 $X$, $Y$와 왼쪽($L$) 및 오른쪽($R$) 자식을 가리키는 포인터를 가집니다.

필요한 모든 연산은 Split과 Merge라는 두 가지 보조 연산만으로 구현합니다.

Split

Split ($T$, $X$) 는 트리 $T$를 두 서브트리 $L$과 $R$(split의 반환값)로 나누며, $L$에는 키가 $X_L \le X$인 모든 원소가, $R$에는 키가 $X_R > X$인 모든 원소가 들어갑니다. 이 연산의 복잡도는 $O (\log N)$이며, 깔끔한 재귀로 구현됩니다.

  1. 루트 노드(R)의 값이 $\le X$이면, L은 적어도 R->L과 R로 구성됩니다. 그다음 R->R에 대해 split을 호출하고, 그 split 결과를 L'과 R'로 둡니다. 마지막으로 L은 L'도 포함하게 되고, R = R'이 됩니다.
  2. 루트 노드(R)의 값이 $> X$이면, R은 적어도 R과 R->R로 구성됩니다. 그다음 R->L에 대해 split을 호출하고, 그 split 결과를 L'과 R'로 둡니다. 마지막으로 L=L'이 되고, R은 R'도 포함하게 됩니다.

따라서 split 알고리즘은 다음과 같습니다.

  1. 루트 노드가 어느 서브트리(왼쪽 또는 오른쪽)에 속할지 결정합니다
  2. 자식 중 하나에 대해 split을 재귀적으로 호출합니다.
  3. 재귀 split 호출의 결과를 재사용하여 최종 결과를 만듭니다.

Merge

Merge ($T_1$, $T_2$) 는 두 서브트리 $T_1$과 $T_2$를 결합하여 새 트리를 반환합니다. 이 연산의 복잡도 역시 $O (\log N)$입니다. 이 연산은 $T_1$과 $T_2$가 정렬되어 있다는 가정(즉, $T_1$의 모든 키 $X$가 $T_2$의 키보다 작다는 가정) 아래에서 동작합니다. 따라서 우선순위 $Y$의 순서를 위반하지 않으면서 이 트리들을 합쳐야 합니다. 이를 위해 루트 노드의 우선순위 $Y$가 더 높은 트리를 루트로 선택하고, 다른 트리와 선택한 루트 노드의 해당 서브트리에 대해 Merge를 재귀적으로 호출합니다.

Insert

이제 Insert ($X$, $Y$) 연산의 구현은 자명해집니다. 먼저 (X를 기준으로 하는 일반적인 이진 탐색 트리에서처럼) 트리를 따라 내려가다가, 우선순위 값이 $Y$보다 작은 첫 번째 노드에서 멈춥니다. 이로써 새 원소를 삽입할 위치를 찾았습니다. 다음으로, 찾은 노드에서 시작하는 서브트리에 대해 Split (T, X) 를 호출하고, 반환된 서브트리 $L$과 $R$을 새 노드의 왼쪽 자식과 오른쪽 자식으로 사용합니다.

또는 초기 트립을 $X$ 기준으로 분할한 뒤 새 노드와 $2$번 병합하는 방식으로도 삽입할 수 있습니다(그림 참조).

Erase

Erase ($X$) 연산의 구현 역시 명확합니다. 먼저 ($X$를 기준으로 하는 일반적인 이진 탐색 트리에서처럼) 트리를 따라 내려가며 삭제하려는 원소를 찾습니다. 노드를 찾으면 그 자식들에 대해 Merge를 호출하고, 연산의 반환값을 삭제하려는 원소의 자리에 넣습니다.

또는 $2$번의 split 연산으로 $X$를 담고 있는 서브트리를 떼어 낸 뒤, 남은 트립들을 병합할 수도 있습니다(그림 참조).

Build

$N$번의 Insert 호출을 사용하여 Build 연산을 $O (N \log N)$ 복잡도로 구현합니다.

Union

Union ($T_1$, $T_2$)의 이론적 복잡도는 $O (M \log (N / M))$이지만, 실제로는 매우 잘 동작하며, 숨은 상수가 아마 매우 작기 때문일 것입니다. 일반성을 잃지 않고 $T_1 \rightarrow Y > T_2 \rightarrow Y$라고 가정합시다. 즉, $T_1$의 루트가 결과의 루트가 됩니다. 결과를 얻으려면 트리 $T_1 \rightarrow L$, $T_1 \rightarrow R$, $T_2$를 $T_1$ 루트의 자식이 될 수 있는 두 개의 트리로 병합해야 합니다. 이를 위해 Split ($T_2$, $T_1\rightarrow X$)을 호출하여 $T_2$를 두 부분 L과 R로 나누고, 이를 $T_1$의 자식들과 재귀적으로 결합합니다. 즉, Union ($T_1 \rightarrow L$, $L$)과 Union ($T_1 \rightarrow R$, $R$)을 호출하여 결과의 왼쪽 서브트리와 오른쪽 서브트리를 얻습니다.

구현

struct item {
    int key, prior;
    item *l, *r;
    item () { }
    item (int key) : key(key), prior(rand()), l(NULL), r(NULL) { }
    item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
};
typedef item* pitem;

다음은 item의 정의입니다. 두 개의 자식 포인터와 정수 키(BST용), 그리고 정수 우선순위(힙용)가 있다는 점에 유의하십시오. 우선순위는 난수 생성기를 사용하여 부여합니다.

void split (pitem t, int key, pitem & l, pitem & r) {
    if (!t)
        l = r = NULL;
    else if (t->key <= key)
        split (t->r, key, t->r, r),  l = t;
    else
        split (t->l, key, l, t->l),  r = t;
}

t는 분할할 트립이고, key는 분할 기준이 되는 BST 값입니다. 결괏값을 어디에서도 return하지 않는다는 점에 유의하십시오. 대신 출력 트립은 l과 r을 통해 기록됩니다. 예를 들면 다음과 같습니다.

pitem l = nullptr, r = nullptr;
split(t, 5, l, r);

이 split 함수는 포인터(pitem)와 그 포인터에 대한 참조(pitem &l)를 모두 사용하기 때문에 이해하기 까다로울 수 있습니다. 함수 호출 split(t, k, l, r)이 의도하는 바를 말로 풀어 이해해 봅시다. 이는 "트립 t를 값 k를 기준으로 두 개의 트립으로 분할하고, 왼쪽 트립은 l에, 오른쪽 트립은 r에 저장하는 것"입니다. 좋습니다! 이제 이전 절에서 분석한 경우 나누기를 사용하여 이 정의를 두 재귀 호출에 적용해 봅시다. (첫 번째 if 조건은 빈 트립에 대한 자명한 기저 사례입니다)

  1. 루트 노드의 값이 $\le$ key일 때는 split (t->r, key, t->r, r)을 호출하며, 이는 "트립 t->r(t의 오른쪽 서브트리)을 값 key를 기준으로 분할하고, 왼쪽 서브트리는 t->r에, 오른쪽 서브트리는 r에 저장하는 것"을 의미합니다. 그 후 l = t로 설정합니다. 이제 결괏값 l에는 t->l, t, 그리고 t->r(방금 수행한 재귀 호출의 결과)이 모두 올바른 순서로 이미 병합되어 있다는 점에 주목하십시오! 잠시 멈추어 이 l과 r의 결과가 앞서 구현 설명에서 논의한 내용과 정확히 일치하는지 확인하십시오.
  2. 루트 노드의 값이 key보다 클 때는 split (t->l, key, l, t->l)을 호출하며, 이는 "트립 t->l(t의 왼쪽 서브트리)을 값 key를 기준으로 분할하고, 왼쪽 서브트리는 l에, 오른쪽 서브트리는 t->l에 저장하는 것"을 의미합니다. 그 후 r = t로 설정합니다. 이제 결괏값 r에는 t->l(방금 수행한 재귀 호출의 결과), t, 그리고 t->r이 모두 올바른 순서로 이미 병합되어 있다는 점에 주목하십시오! 잠시 멈추어 이 l과 r의 결과가 앞서 구현 설명에서 논의한 내용과 정확히 일치하는지 확인하십시오.

그래도 구현을 이해하기 어렵다면 귀납적으로 살펴보아야 합니다. 즉, 재귀 호출을 계속해서 분해하려고 하지 마십시오. split 구현이 빈 트립에서 올바르게 동작한다고 가정한 다음, 노드가 하나인 트립, 노드가 두 개인 트립 등에 대해 차례로 실행해 보면서, 매번 더 작은 트립에서는 split이 올바르게 동작한다는 사실을 다시 활용하십시오.

void insert (pitem & t, pitem it) {
    if (!t)
        t = it;
    else if (it->prior > t->prior)
        split (t, it->key, it->l, it->r),  t = it;
    else
        insert (t->key <= it->key ? t->r : t->l, it);
}

void merge (pitem & t, pitem l, pitem r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
}

void erase (pitem & t, int key) {
    if (t->key == key) {
        pitem th = t;
        merge (t, t->l, t->r);
        delete th;
    }
    else
        erase (key < t->key ? t->l : t->r, key);
}

pitem unite (pitem l, pitem r) {
    if (!l || !r)  return l ? l : r;
    if (l->prior < r->prior)  swap (l, r);
    pitem lt, rt;
    split (r, l->key, lt, rt);
    l->l = unite (l->l, lt);
    l->r = unite (l->r, rt);
    return l;
}

서브트리 크기 유지하기

트립의 기능을 확장하려면 각 노드의 서브트리에 있는 노드 수를 저장해야 하는 경우가 많습니다 - item 구조체의 int cnt 필드입니다. 예를 들어, 이를 사용하면 트리에서 K번째로 큰 원소를 $O (\log N)$에 찾거나, 정렬된 리스트에서 원소의 인덱스를 같은 복잡도로 찾을 수 있습니다. 이러한 연산의 구현은 일반적인 이진 탐색 트리의 경우와 같습니다.

트리가 변경되면(노드가 추가되거나 제거되는 등) 일부 노드의 cnt도 그에 맞게 갱신해야 합니다. 두 개의 함수를 만들겠습니다. cnt()는 cnt의 현재 값을 반환하되 노드가 존재하지 않으면 0을 반환하고, upd_cnt()는 자식 L과 R의 cnt 값이 이미 갱신되어 있다고 가정하고 이 노드의 cnt 값을 갱신합니다. cnt 값을 최신 상태로 유지하려면 insert, erase, split, merge의 끝에 upd_cnt() 호출을 추가하는 것으로 충분하다는 점은 자명합니다.

int cnt (pitem t) {
    return t ? t->cnt : 0;
}

void upd_cnt (pitem t) {
    if (t)
        t->cnt = 1 + cnt(t->l) + cnt (t->r);
}

오프라인 모드에서 $O (N)$에 트립 구성하기

정렬된 키 목록이 주어지면, 키를 하나씩 삽입하여 $O(N \log N)$이 걸리는 방식보다 빠르게 트립을 구성할 수 있습니다. 키가 정렬되어 있으므로 균형 이진 탐색 트리를 선형 시간에 쉽게 구성할 수 있습니다. 힙 값 $Y$는 무작위로 초기화한 뒤 키 $X$와 독립적으로 힙화하여 $O(N)$에 힙을 구성할 수 있습니다.

void heapify (pitem t) {
    if (!t) return;
    pitem max = t;
    if (t->l != NULL && t->l->prior > max->prior)
        max = t->l;
    if (t->r != NULL && t->r->prior > max->prior)
        max = t->r;
    if (max != t) {
        swap (t->prior, max->prior);
        heapify (max);
    }
}

pitem build (int * a, int n) {
    // Construct a treap on values {a[0], a[1], ..., a[n - 1]}
    if (n == 0) return NULL;
    int mid = n / 2;
    pitem t = new item (a[mid], rand ());
    t->l = build (a, mid);
    t->r = build (a + mid + 1, n - mid - 1);
    heapify (t);
    upd_cnt(t);
    return t;
}

참고: upd_cnt(t) 호출은 서브트리 크기가 필요한 경우에만 필요합니다.

위의 방법은 항상 완벽하게 균형 잡힌 트리를 만들어 주므로 일반적으로 실용적인 목적에는 좋지만, 각 노드에 처음 할당된 우선순위를 보존하지 못한다는 대가가 따릅니다. 따라서 이 방법으로는 다음 문제를 해결할 수 없습니다:

acmsguru - Cartesian Tree

쌍 $(x_i, y_i)$의 수열이 주어질 때, 이들로 데카르트 트리를 구성하십시오. 모든 $x_i$와 모든 $y_i$는 서로 다릅니다.

이 문제에서는 우선순위가 무작위가 아니므로, 정점을 하나씩 삽입하기만 하면 이차 시간 풀이가 될 수 있다는 점에 유의하십시오.

가능한 풀이 중 하나는 각 원소에 대해, 그 원소보다 우선순위가 작은 원소 중 왼쪽과 오른쪽으로 가장 가까운 원소를 찾는 것입니다. 이 두 원소 중 우선순위가 더 큰 원소가 현재 원소의 부모가 되어야 합니다.

이 문제는 최소 스택 변형을 이용하여 선형 시간에 해결할 수 있습니다. 아래의 구성은 위의 일반적인 트립 구현에서 사용한 최대 힙 규칙과 달리 우선순위에 최소 힙 규칙을 사용하며, item에 nullptr로 초기화된 부모 포인터 p가 추가되어 있다고 가정합니다:

void connect(auto from, auto to) {
    vector<pitem> st;
    for(auto it: ranges::subrange(from, to)) {
        while(!st.empty() && st.back()->prior > it->prior) {
            st.pop_back();
        }
        if(!st.empty()) {
            if(!it->p || it->p->prior < st.back()->prior) {
                it->p = st.back();
            }
        }
        st.push_back(it);
    }
}

pitem build(int *x, int *y, int n) {
    vector<pitem> nodes(n);
    for(int i = 0; i < n; i++) {
        nodes[i] = new item(x[i], y[i]);
    }
    connect(nodes.begin(), nodes.end());
    connect(nodes.rbegin(), nodes.rend());
    for(int i = 0; i < n; i++) {
        if(nodes[i]->p) {
            if(nodes[i]->p->key < nodes[i]->key) {
                nodes[i]->p->r = nodes[i];
            } else {
                nodes[i]->p->l = nodes[i];
            }
        }
    }
    return nodes[min_element(y, y + n) - y];
}

암시적 트립

암시적 트립은 일반적인 트립을 간단히 변형한 것으로, 매우 강력한 자료 구조입니다. 사실 암시적 트립은 다음 연산들이 구현된 배열로 볼 수 있습니다(모두 온라인 모드에서 $O (\log N)$에 동작합니다):

  • 배열의 임의의 위치에 원소 삽입
  • 임의의 원소 제거
  • 임의의 구간에서 합, 최솟값 / 최댓값 원소 등을 구하기
  • 임의의 구간에 대한 덧셈, 칠하기
  • 임의의 구간의 원소 뒤집기

핵심 아이디어는 키가 배열에서 원소의 0부터 시작하는 인덱스가 되어야 한다는 것입니다. 하지만 이 값들을 명시적으로 저장하지는 않습니다(그렇게 하면, 예를 들어 원소 하나를 삽입할 때 트리의 $O (N)$개 노드에서 키가 변경됩니다).

노드의 키는 그 노드보다 작은 노드의 개수라는 점에 유의하십시오(이러한 노드는 그 노드의 왼쪽 서브트리뿐만 아니라 조상들의 왼쪽 서브트리에도 존재할 수 있습니다). 좀 더 구체적으로, 어떤 노드 T의 암시적 키는 이 노드의 왼쪽 서브트리에 있는 정점의 개수 $cnt (T \rightarrow L)$에, T가 P의 오른쪽 서브트리에 있는 경우 노드 T의 각 조상 P에 대한 비슷한 값 $cnt (P \rightarrow L) + 1$을 더한 것입니다.

이제 현재 노드의 암시적 키를 빠르게 계산하는 방법이 분명해졌습니다. 모든 연산에서 트리를 따라 내려가며 노드에 도달하므로, 이 합을 누적하여 함수에 전달하기만 하면 됩니다. 왼쪽 서브트리로 이동하면 누적된 합은 변하지 않고, 오른쪽 서브트리로 이동하면 $cnt (T \rightarrow L) +1$만큼 증가합니다.

다음은 Split과 Merge의 새로운 구현입니다:

void merge (pitem & t, pitem l, pitem r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
    upd_cnt (t);
}

void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
    if (!t)
        return void( l = r = 0 );
    int cur_key = add + cnt(t->l); //implicit key
    if (key <= cur_key)
        split (t->l, l, t->l, key, add),  r = t;
    else
        split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
    upd_cnt (t);
}

위 구현에서 $split(T, T_1, T_2, k)$를 호출하고 나면, 트리 $T_1$은 $T$의 처음 $k$개 원소(즉, 암시적 키가 $k$보다 작은 원소들)로 구성되고 $T_2$는 나머지 모든 원소로 구성됩니다.

이제 암시적 트립에서의 다양한 연산 구현을 살펴봅시다:

  • 원소 삽입.
    위치 $pos$에 원소를 삽입해야 한다고 가정합시다. 트립을 배열 $[0..pos-1]$과 $[pos..sz]$에 해당하는 두 부분으로 나눕니다. 이를 위해 $split(T, T_1, T_2, pos)$를 호출합니다. 그런 다음 $merge(T_1, T_1, \text{new item})$을 호출하여 트리 $T_1$과 새 정점을 합칠 수 있습니다(모든 전제 조건이 충족됨을 쉽게 알 수 있습니다). 마지막으로 $merge(T, T_1, T_2)$를 호출하여 트리 $T_1$과 $T_2$를 다시 $T$로 합칩니다.
  • 원소 삭제.
    이 연산은 더욱 쉽습니다. 삭제할 원소 $T$를 찾고, 그 자식 $L$과 $R$을 병합한 뒤, 원소 $T$를 병합 결과로 대체합니다. 사실 암시적 트립에서의 원소 삭제는 일반 트립에서와 완전히 동일합니다.
  • 구간에서 합 / 최솟값 등을 구하기.
    먼저, 이 노드의 서브트리에 대한 대상 함수의 값을 저장하기 위해 item 구조체에 추가 필드 $F$를 만듭니다. 이 필드는 서브트리 크기를 유지하는 것과 비슷한 방식으로 쉽게 유지할 수 있습니다. 자식들의 값을 바탕으로 노드의 이 값을 계산하는 함수를 만들고, 트리를 수정하는 모든 함수의 끝에 이 함수의 호출을 추가하면 됩니다.
    둘째로, 임의의 구간 $[A; B]$에 대한 쿼리를 처리하는 방법을 알아야 합니다.
    구간 $[A; B]$에 해당하는 트리의 부분을 얻으려면 $split(T, T_2, T_3, B+1)$을 호출한 다음 $split(T_2, T_1, T_2, A)$를 호출해야 합니다. 그러면 $T_2$는 구간 $[A; B]$에 속한 모든 원소로만 구성됩니다. 따라서 쿼리에 대한 답은 $T_2$의 루트의 필드 $F$에 저장됩니다. 쿼리에 답한 후에는 $merge(T, T_1, T_2)$와 $merge(T, T, T_3)$를 호출하여 트리를 복원해야 합니다.
  • 구간에 대한 덧셈 / 칠하기.
    앞 문단과 비슷하게 진행하되, 필드 F 대신 서브트리에 더해진 값(또는 서브트리를 칠한 값)을 담는 필드 add를 저장합니다. 어떤 연산을 수행하기 전에 이 값을 올바르게 "push"해야 합니다. 즉, $T \rightarrow L \rightarrow add$와 $T \rightarrow R \rightarrow add$를 변경하고, 부모 노드의 add를 비워야 합니다. 이렇게 하면 트리에 어떤 변경이 일어나도 정보가 손실되지 않습니다.
  • 구간 뒤집기.
    이것도 앞의 연산과 비슷합니다. 불리언 플래그 rev를 추가하고, 현재 노드의 서브트리를 뒤집어야 할 때마다 이 플래그를 토글해야 합니다. 이 값을 "push"하는 것은 조금 복잡합니다. 이 노드의 자식들을 서로 바꾸고, 자식들의 이 플래그를 토글합니다.

다음은 구간 뒤집기를 지원하는 암시적 트립의 구현 예시입니다. 각 노드에는 현재 위치에 있는 배열 원소의 실제 값인 value라는 필드를 저장합니다. 또한 암시적 트립의 현재 상태에 해당하는 배열을 출력하는 함수 output()의 구현도 제공합니다.

typedef struct item * pitem;
struct item {
    int prior, value, cnt;
    bool rev;
    pitem l, r;
};

int cnt (pitem it) {
    return it ? it->cnt : 0;
}

void upd_cnt (pitem it) {
    if (it)
        it->cnt = cnt(it->l) + cnt(it->r) + 1;
}

void push (pitem it) {
    if (it && it->rev) {
        it->rev = false;
        swap (it->l, it->r);
        if (it->l)  it->l->rev ^= true;
        if (it->r)  it->r->rev ^= true;
    }
}

void merge (pitem & t, pitem l, pitem r) {
    push (l);
    push (r);
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
    upd_cnt (t);
}

void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
    if (!t)
        return void( l = r = 0 );
    push (t);
    int cur_key = add + cnt(t->l);
    if (key <= cur_key)
        split (t->l, l, t->l, key, add),  r = t;
    else
        split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
    upd_cnt (t);
}

void reverse (pitem t, int l, int r) {
    pitem t1, t2, t3;
    split (t, t1, t2, l);
    split (t2, t2, t3, r-l+1);
    t2->rev ^= true;
    merge (t, t1, t2);
    merge (t, t, t3);
}

void output (pitem t) {
    if (!t)  return;
    push (t);
    output (t->l);
    printf ("%d ", t->value);
    output (t->r);
}

참고 문헌

연습 문제