FHQ-Treap の学習ノート

Treap は Tree と Heap を組み合わせたデータ構造です。

Treap は弱いバランスの取れた二分探索木であり、カーネルツリーとして見なせます。各ノードには (Key, Value) という2つの値を持ち、Key は二分探索木の性質を満たし、Value はヒープの性質を満たします（通常は最小ヒープ）。Key は実際の情報であり、Value はランダムな値で、木の高さが log n になるように保証するために使用されます。

回転 Treap は回転操作でバランスを保つが、非回転 Treap である FHQ-Treap は分割と結合によってバランスを保ちます。

分割（Split）

機能：ある値 k に対して、Treap を2つの部分に分割します。1つ目の部分はすべての Key が k より小さいもので構成され、2つ目の部分はすべての Key が k 以上になります。

現在の Treap の根ノードを考慮します。もし Key が k より小さいなら、そのノードおよび左部分木は1つ目の Treap に含まれ、右部分木は再帰的に処理されます。逆に Key が k 以上であれば、そのノードおよび右部分木は2つ目の Treap に含まれ、左部分木を再帰的に処理します。木が空の場合、分割は行われません。

実装では参照引数を使用します。コード例は以下の通りです：

void split(int now, int k, int &u, int &v) {
    if (now == 0) { u = v = 0; return; }
    if (key[now] < k) {
        u = now;
        split(rs[now], k, rs[now], v);
    } else {
        v = now;
        split(ls[now], k, u, ls[now]);
    }
    push_up(now);
    return;
}

結合（Merge）

機能：2つの Treap を結合します。ただし、1つ目の Treap のすべての Key が 2つ目の Treap の Key より小さい必要があります。

結合する2つの Treap の根ノードを比較します。もし1つ目の Root の Value が小さい場合、そのノードを新しい根にして、右部分木と2つ目の Treap を結合します。逆に、2つ目の Root の Value が小さい場合、左部分木と1つ目の Treap を結合します。どちらかの Treap が空の場合、もう片方を返します。

コード例は以下の通りです：

int merge(int u, int v) {
    if (u == 0 || v == 0) return u + v;
    if (val[u] < val[v]) {
        rs[u] = merge(rs[u], v);
        push_up(u);
        return u;
    } else {
        ls[v] = merge(u, ls[v]);
        push_up(v);
        return v;
    }
}

Split と Merge を用いることで、平衡木の基本操作を実現できます。

基本操作

挿入

挿入する値を k とします。

まず k で Split してから、新しく Key = k のノードを作成し、第一の木、新規ノード、第二の木を順番に Merge します。

void insert(int k) {
    int u, v;
    split(root, k, u, v);
    root = merge(merge(u, new_node(k)), v);
    return;
}

削除

削除する値を k とします。

まず k で Split し、次に k+1 で Split します。これにより3つの木を得られます。2つ目の木に含まれるノードの Key は k です。この木の左右の子を Merge することで、根ノードを削除します。その後、3つの木を再び Merge します。

void erase(int k) {
    int u, v, w;
    split(root, k, u, v);
    split(v, k + 1, v, w);
    v = merge(ls[v], rs[v]);
    root = merge(merge(u, v), w);
    return;
}

ランクの取得

k を基準に Split して、1つ目の木のサイズを取得します。

int order_of_key(int k) {
    int u, v;
    split(root, k, u, v);
    int ans = size[u] + 1;
    root = merge(u, v);
    return ans;
}

ランク k の値の取得

BST の方法で実装します。

int find_by_order(int rk) {
    int now = root;
    while (now) {
        if (rk == size[ls[now]] + 1) return key[now];
        else if (rk <= size[ls[now]]) now = ls[now];
        else {
            rk -= size[ls[now]] + 1;
            now = rs[now];
        }
    }
    return -1;
}

前駆と後続の検索

前駆は k のランクより1つ前の値、後続は k のランクより1つ後の値です。

int find_pre(int k) { return find_by_order(order_of_key(k) - 1); }
int find_suf(int k) { return find_by_order(order_of_key(k + 1)); }

完全なコード

struct FHQ_Treap {
    int root, cnt;
    int key[1100005], val[1100005], size[1100005];
    int ls[1100005], rs[1100005];
    int new_node(int k) { cnt++; key[cnt] = k; val[cnt] = gen(); size[cnt] = 1; return cnt; }
    void push_up(int now) { size[now] = size[ls[now]] + size[rs[now]] + 1; return; }
    int merge(int u, int v) {
        if (u == 0 || v == 0) return u + v;
        if (val[u] < val[v]) {
            rs[u] = merge(rs[u], v);
            push_up(u);
            return u;
        } else {
            ls[v] = merge(u, ls[v]);
            push_up(v);
            return v;
        }
    }
    void split(int now, int k, int &u, int &v) {
        if (now == 0) { u = v = 0; return; }
        if (key[now] < k) {
            u = now;
            split(rs[now], k, rs[now], v);
        } else {
            v = now;
            split(ls[now], k, u, ls[now]);
        }
        push_up(now);
        return;
    }
    void insert(int k) {
        int u, v;
        split(root, k, u, v);
        root = merge(merge(u, new_node(k)), v);
        return;
    }
    void erase(int k) {
        int u, v, w;
        split(root, k, u, v);
        split(v, k + 1, v, w);
        v = merge(ls[v], rs[v]);
        root = merge(merge(u, v), w);
        return;
    }
    int order_of_key(int k) {
        int u, v;
        split(root, k, u, v);
        int ans = size[u] + 1;
        root = merge(u, v);
        return ans;
    }
    int find_by_order(int rk) {
        int now = root;
        while (now) {
            if (rk == size[ls[now]] + 1) return key[now];
            else if (rk <= size[ls[now]]) now = ls[now];
            else {
                rk -= size[ls[now]] + 1;
                now = rs[now];
            }
        }
        return -1;
    }
    int find_pre(int k) { return find_by_order(order_of_key(k) - 1); }
    int find_suf(int k) { return find_by_order(order_of_key(k + 1)); }
};

アートバランス木

問題リンク：https://www.luogu.com.cn/problem/P3391

並べ替えられた数列を維持するためのデータ構造を書く。区間反転操作をサポートする。

前述の平衡木の基本操作に基づき、操作範囲を Split して、処理後に Merge します。

しかし、配列は常に整列されていないため、Treap は値で管理できません。代わりに、サブツリーのサイズを使って分割します。つまり、Treap を2つの木に分割し、1つの木のサイズが特定の値に等しくなるようにします。

void split(int now, int sz, int &u, int &v) {
    if (now == 0) { u = v = 0; return; }
    if (size[ls[now]] < sz) {
        u = now;
        split(rs[now], sz - size[ls[now]] - 1, rs[now], v);
    } else {
        v = now;
        split(ls[now], sz, u, ls[now]);
    }
    push_up(now);
    return;
}

区間反転については、線分木の遅延伝播のように、各ノードにラジオマークを設けます。訪問時に push_down を呼び出します。

void reverse(int l, int r) {
    int u, v, w;
    split(root, l - 1, u, v);
    split(v, r - l + 1, v, w);
    lzy[v] ^= 1;
    swap(ls[v], rs[v]);
    merge(merge(u, v), w);
    return;
}

完全なコード：

//Think twice,code once.
#include<chrono>
#include<random>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int n,m;
mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
struct Fido_Puppy_Treap {
    int root,cnt;
    int key[100005],val[100005],size[100005],lzy[100005];
    int ls[100005],rs[100005];
    int new_node(int k) {cnt++;key[cnt]=k;val[cnt]=gen();size[cnt]=1;return cnt;}
    void push_up(int now) {size[now]=size[ls[now]]+size[rs[now]]+1;return ;}
    void push_down(int now) {
        swap(ls[ls[now]],rs[ls[now]]);
        swap(ls[rs[now]],rs[rs[now]]);
        lzy[ls[now]]^=1;lzy[rs[now]]^=1;
        lzy[now]=0;
        return ;
    }
    int merge(int u,int v) {
        if (u==0||v==0) return u+v;
        if (lzy[u]) push_down(u);
        if (lzy[v]) push_down(v);
        if (val[u]<val[v]) {rs[u]=merge(rs[u],v);push_up(u);return u;}
        else {ls[v]=merge(u,ls[v]);push_up(v);return v;}
    }
    void split(int now,int sz,int &u,int &v) {
        if (now==0) {u=v=0;return ;}
        if (lzy[now]) push_down(now);
        if (size[ls[now]]<sz) u=now,split(rs[now],sz-size[ls[now]]-1,rs[now],v);
        else v=now,split(ls[now],sz,u,ls[now]);
        push_up(now);
        return ;
    }
    void insert(int k) {root=merge(root,new_node(k));return ;}
    void reverse(int l,int r) {
        int u,v,w;
        split(root,l-1,u,v);
        split(v,r-l+1,v,w);
        lzy[v]^=1;
        swap(ls[v],rs[v]);
        merge(merge(u,v),w);
        return ;
    }
    void print(int now) {
        if (now==0) return ;
        if (lzy[now]) push_down(now);
        print(ls[now]);
        printf("%d ",now);
        print(rs[now]);
        return ;
    }
}tr;

int main() {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) tr.insert(i);
    while (m--) {
        int l,r;
        scanf("%d%d",&l,&r);
        tr.reverse(l,r);
    }
    tr.print(tr.root);
    puts("");
    return 0;
}