FHQ-Treap（または無旋Treap）は、ノードの回転操作を行わずに「分割」と「併合」という2つのプリミティブな操作のみを用いてバランスを維持する二分探索木です。このデータ構造は、各ノードに「値」と「ランダムな優先度」を持たせます。値は二分探索木の性質（左の子 < 親 < 右の子）を満たし、優先度はヒープの性質（親が子よりも高い優先度を持つ）を満たすように管理されます。優先度がランダムであるため、木の期待深さは O(log N) となり、効率的な検索や更新が可能になります。

データ構造の定義

FHQ-Treapの各ノードには、子ノードへのポインタ、格納する値、ランダムに生成された優先度、および部分木のサイズを保持させます。静的な配列を使用してノードを管理する実装はシンプルで高速です。

const int MAX_N = 100005;
struct Node {
    int l, r;       // 左右の子ノードのインデックス
    int val;        // ノードの値（BSTのキー）
    int prio;       // 優先度（Heapのキー、ランダム）
    int size;       // 部分木のサイズ
} tr[MAX_N];

std::mt19937 rng(19260817); // 乱数生成器
int node_cnt;               // 使用中のノード数
int root;                   // 木の根

基本操作の実装

ノードの生成と更新

新しいノードを作成する際は、値を設定し、優先度をランダムに生成します。また、部分木のサイズを計算するために `pushUp` 関数を定義します。

// 新しいノードを生成してインデックスを返す
int newNode(int v) {
    tr[++node_cnt].val = v;
    tr[node_cnt].prio = rng();
    tr[node_cnt].size = 1;
    tr[node_cnt].l = tr[node_cnt].r = 0;
    return node_cnt;
}

// ノードのサイズ情報を更新
void pushUp(int p) {
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + 1;
}

分割 (Split)

FHQ-Treapの中核となる操作です。指定された値 `k` を基準に、木を2つの木 `x` と `y` に分割します。`x` は `k` 以下の値を持つノードからなる木、`y` は `k` より大きい値を持つノードからなる木となります。この操作は再帰的に行われます。

// 値による分割：木 p を (k以下) と (kより大きい) に分割し、x と y に入れる
void split(int p, int k, int &x, int &y) {
    if (!p) {
        x = y = 0;
        return;
    }
    // 現在のノードの値が k 以下の場合、左部分木と現在のノードは x 側に属する
    if (tr[p].val <= k) {
        x = p;
        split(tr[p].r, k, tr[p].r, y);
    } else {
        // それ以外の場合、右部分木と現在のノードは y 側に属する
        y = p;
        split(tr[p].l, k, x, tr[p].l);
    }
    pushUp(p);
}

併合 (Merge)

2つの木 `x` と `y` を1つの木に併合します。前提条件として、`x` 内のすべての値は `y` 内のすべての値より小さくなければなりません。併合の際は、優先度に基づいてヒープ構造を維持します（ここでは優先度が高いものを根とする大根堆とします）。

// 併合：x (小さい側) と y (大きい側) を併合して根を返す
int merge(int x, int y) {
    if (!x || !y) return x + y;
    // 優先度が高い方を根として、もう一方の子と再帰的に併合する
    if (tr[x].prio > tr[y].prio) {
        tr[x].r = merge(tr[x].r, y);
        pushUp(x);
        return x;
    } else {
        tr[y].l = merge(x, tr[y].l);
        pushUp(y);
        return y;
    }
}

主要なクエリの実装

上記の基本操作を組み合わせることで、挿入、削除、順位查询などを実装できます。

挿入

挿入する値 `v` で木を分割し、新規ノードを挟んで再び併合します。

void insert(int v) {
    int x, y;
    // v 以下と v より大きい部分に分割
    split(root, v, x, y);
    // 新しいノードを作成し、x -> new_node -> y の順で併合
    root = merge(merge(x, newNode(v)), y);
}

削除

削除する値 `v` で木を3分割し、該当する部分木の根（ノード）を取り除いてから併合します。

void erase(int v) {
    int x, y, z;
    // v 未満、v 以下、v より大きい部分に分割
    split(root, v, x, z);
    split(x, v - 1, x, y);
    // y の根が削除対象のノードなので、左右の子を直接併合して根を消す
    y = merge(tr[y].l, tr[y].r);
    // 残りを併合
    root = merge(merge(x, y), z);
}

値による順位の取得

値 `v` が全体で何番目に小さいかを求めます。`v-1` で分割し、左側の木のサイズを利用します。

int getRank(int v) {
    int x, y;
    split(root, v - 1, x, y);
    int res = tr[x].size + 1;
    root = merge(x, y); // 元に戻す
    return res;
}

順位による値の取得 (k-th number)

指定された順位 `k` の値を取得します。部分木のサイズを見ながら探索します。

int getVal(int k) {
    int p = root;
    while (p) {
        int left_size = tr[tr[p].l].size;
        if (left_size + 1 == k) {
            return tr[p].val;
        } else if (left_size >= k) {
            p = tr[p].l;
        } else {
            k -= left_size + 1;
            p = tr[p].r;
        }
    }
    return -1; // 見つからない場合
}

前駆と後続

指定された値 `v` より小さい最大の値（前駆）と、大きい最小の値（後続）を求めます。

int getPrev(int v) {
    int x, y;
    split(root, v - 1, x, y);
    int p = x;
    // x の最大値を探すため、右の子へ辿る
    while (tr[p].r) p = tr[p].r;
    int res = tr[p].val;
    root = merge(x, y);
    return res;
}

int getNext(int v) {
    int x, y;
    split(root, v, x, y);
    int p = y;
    // y の最小値を探すため、左の子へ辿る
    while (tr[p].l) p = tr[p].l;
    int res = tr[p].val;
    root = merge(x, y);
    return res;
}

通常の平衡木問題への適用例

以下は、挿入、削除、順位查询、値查询、前駆・後続查询を含む典型的な問題に対する完全な実装例です。

#include <iostream>
#include <algorithm>
#include <random>

using namespace std;

const int MAX_N = 100005;

struct Node {
    int l, r, val, prio, size;
} tr[MAX_N];

mt19937 rng(19260817);
int node_cnt, root;

void pushUp(int p) {
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + 1;
}

int newNode(int v) {
    tr[++node_cnt].val = v;
    tr[node_cnt].prio = rng();
    tr[node_cnt].size = 1;
    tr[node_cnt].l = tr[node_cnt].r = 0;
    return node_cnt;
}

void split(int p, int k, int &x, int &y) {
    if (!p) { x = y = 0; return; }
    if (tr[p].val <= k) {
        x = p;
        split(tr[p].r, k, tr[p].r, y);
    } else {
        y = p;
        split(tr[p].l, k, x, tr[p].l);
    }
    pushUp(p);
}

int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (tr[x].prio > tr[y].prio) {
        tr[x].r = merge(tr[x].r, y);
        pushUp(x);
        return x;
    } else {
        tr[y].l = merge(x, tr[y].l);
        pushUp(y);
        return y;
    }
}

void insert(int v) {
    int x, y;
    split(root, v, x, y);
    root = merge(merge(x, newNode(v)), y);
}

void erase(int v) {
    int x, y, z;
    split(root, v, x, z);
    split(x, v - 1, x, y);
    y = merge(tr[y].l, tr[y].r);
    root = merge(merge(x, y), z);
}

int getRank(int v) {
    int x, y;
    split(root, v - 1, x, y);
    int res = tr[x].size + 1;
    merge(x, y);
    return res;
}

int getVal(int k) {
    int p = root;
    while (p) {
        int left_sz = tr[tr[p].l].size;
        if (left_sz + 1 == k) return tr[p].val;
        if (left_sz >= k) p = tr[p].l;
        else {
            k -= left_sz + 1;
            p = tr[p].r;
        }
    }
    return -1;
}

int getPrev(int v) {
    int x, y;
    split(root, v - 1, x, y);
    int p = x;
    while (tr[p].r) p = tr[p].r;
    int res = tr[p].val;
    merge(x, y);
    return res;
}

int getNext(int v) {
    int x, y;
    split(root, v, x, y);
    int p = y;
    while (tr[p].l) p = tr[p].l;
    int res = tr[p].val;
    merge(x, y);
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    while (n--) {
        int opt, x;
        cin >> opt >> x;
        if (opt == 1) insert(x);
        else if (opt == 2) erase(x);
        else if (opt == 3) cout << getRank(x) << '\n';
        else if (opt == 4) cout << getVal(x) << '\n';
        else if (opt == 5) cout << getPrev(x) << '\n';
        else cout << getNext(x) << '\n';
    }
    return 0;
}

応用：区間反転操作と遅延伝播

FHQ-Treapは区間操作にも対応できます。ここでは、特定の区間を反転させる操作を実装します。区間操作を行うには、Split操作を「値」ではなく「サイズ（ノード数）」で行う必要があります。また、区間の反転を効率的に行うために、Lazy Tag（遅延評価マーク）を用いて、実際に子ノードを入れ替えるタイミングをアクセス時まで遅らせます。

区間操作のための構造体と関数の修正

構造体に `rev`（反転フラグ）を追加し、`split` 操作をサイズ基準に変更します。また、フラグを下に伝播させる `pushDown` 関数を実装します。

struct Node {
    int l, r, val, prio, size;
    bool rev; // 反転フラグ
} tr[MAX_N];

// フラグの伝播
void pushDown(int p) {
    if (tr[p].rev) {
        swap(tr[p].l, tr[p].r);         // 左右の子を入れ替え
        tr[tr[p].l].rev ^= 1;           // フラグを子に伝播
        tr[tr[p].r].rev ^= 1;
        tr[p].rev = false;              // 現在ノードのフラグを解除
    }
}

// サイズによる分割：左の木に k 個のノードを含めるように分割
void split(int p, int k, int &x, int &y) {
    if (!p) { x = y = 0; return; }
    pushDown(p); // 分割前にフラグを処理
    if (tr[tr[p].l].size + 1 <= k) {
        x = p;
        split(tr[p].r, k - tr[tr[p].l].size - 1, tr[p].r, y);
    } else {
        y = p;
        split(tr[p].l, k, x, tr[p].l);
    }
    pushUp(p);
}

// Merge でもフラグ伝播を考慮
int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (tr[x].prio > tr[y].prio) {
        pushDown(x);
        tr[x].r = merge(tr[x].r, y);
        pushUp(x);
        return x;
    } else {
        pushDown(y);
        tr[y].l = merge(x, tr[y].l);
        pushUp(y);
        return y;
    }
}

区間反転のロジック

区間 `[l, r]` を反転させるには、木を ` [1, l-1]`、`[l, r]`、`[r+1, N]` の3つの部分に分割し、中央の部分の `rev` フラグを立ててから再び併合します。

void reverseRange(int l, int r) {
    int x, y, z;
    split(root, r, x, z);       // x: [1, r], z: [r+1, N]
    split(x, l - 1, x, y);      // x: [1, l-1], y: [l, r]
    tr[y].rev ^= 1;             // 区間 y を反転マーク
    root = merge(merge(x, y), z); // 併合
}

// 中間順巡回で出力（確認用）
void inorder(int p) {
    if (!p) return;
    pushDown(p);
    inorder(tr[p].l);
    cout << tr[p].val << " ";
    inorder(tr[p].r);
}

区間反転問題への適用例

初期状態で 1 から N までの数が昇順に並んでおり、複数の区間反転クエリを受け取った後の最終的な数列を出力する問題に対する実装です。

#include <iostream>
#include <algorithm>
#include <random>

using namespace std;

const int MAX_N = 100005;

struct Node {
    int l, r, val, prio, size;
    bool rev;
} tr[MAX_N];

mt19937 rng(19260817);
int node_cnt, root;

void pushUp(int p) {
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + 1;
}

void pushDown(int p) {
    if (tr[p].rev) {
        swap(tr[p].l, tr[p].r);
        tr[tr[p].l].rev ^= 1;
        tr[tr[p].r].rev ^= 1;
        tr[p].rev = false;
    }
}

int newNode(int v) {
    tr[++node_cnt].val = v;
    tr[node_cnt].prio = rng();
    tr[node_cnt].size = 1;
    tr[node_cnt].l = tr[node_cnt].r = 0;
    tr[node_cnt].rev = false;
    return node_cnt;
}

void split(int p, int k, int &x, int &y) {
    if (!p) { x = y = 0; return; }
    pushDown(p);
    if (tr[tr[p].l].size + 1 <= k) {
        x = p;
        split(tr[p].r, k - tr[tr[p].l].size - 1, tr[p].r, y);
    } else {
        y = p;
        split(tr[p].l, k, x, tr[p].l);
    }
    pushUp(p);
}

int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (tr[x].prio > tr[y].prio) {
        pushDown(x);
        tr[x].r = merge(tr[x].r, y);
        pushUp(x);
        return x;
    } else {
        pushDown(y);
        tr[y].l = merge(x, tr[y].l);
        pushUp(y);
        return y;
    }
}

void reverseRange(int l, int r) {
    int x, y, z;
    split(root, r, x, z);
    split(x, l - 1, x, y);
    tr[y].rev ^= 1;
    root = merge(merge(x, y), z);
}

void printInorder(int p) {
    if (!p) return;
    pushDown(p);
    printInorder(tr[p].l);
    cout << tr[p].val << " ";
    printInorder(tr[p].r);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    
    // 1からNまでを挿入して初期構築
    for (int i = 1; i <= n; ++i) {
        root = merge(root, newNode(i));
    }
    
    while (m--) {
        int l, r;
        cin >> l >> r;
        reverseRange(l, r);
    }
    
    printInorder(root);
    cout << endl;
    return 0;
}