スプレイ木の概要

スプレイ木は、動的データ構造の一種であり、二叉探索木のバランスを保つための手法です。Daniel Sleator と Robert Tarjan によって提案されました。その特徴として、明示的なバランス操作を行わずとも、アクセスパターンの履歴に基づいて自動的に調整が行われる点が挙げられます。

この構造では、最近参照された要素を根へと移動させる「スプレイ」操作を実行することで、特定キーへのアクセス時間を最小化します。理論的には、平均時間計算量が對数級になることが証明されています。

基本構造と変換処理

スプレイ木において最も重要な二つの操作は、単一回転（Rotate）とスプレイ（Splay）です。回転操作は部分木の左右関係を入れ替える際、インオーダー周回順序（中序走査順）を変化させないよう注意が必要です。

#include<cstdio>
#include<cstdlib>

const int MAX_NODES = 500100;
const int MIN_VAL = -2147483647;
const int MAX_VAL = 2147483647;

struct TreeNode {
    int left, right, parent;
    int val;
    int count;      // 重複カウント
    int size;       // サブツリーサイズ
} tree[MAX_NODES];

int main_node = 0;
int nodes_count = 0;

// サイズ情報を更新
void refresh_size(int u) {
    tree[u].size = tree[tree[u].left].size + 
                   tree[tree[u].right].size + 
                   tree[u].count;
}

// 回転操作：x を支点に z の子から y の子へ移動させる
void perform_rotate(int x) {
    int y = tree[x].parent;
    int z = tree[y].parent;
    int direction = (tree[y].right == x); 
    
    // 親の親との接続変更
    tree[z].child(z == tree[z].right ? z : 0) = x; //簡略化のため論理
    tree[x].parent = z;
    
    // y と x の連結変更
    tree[y].child(direction) = tree[x].child(1 ^ direction);
    if(tree[x].child(1 ^ direction)) {
        tree[tree[x].child(1 ^ direction)].parent = y;
    }
    
    tree[x].child(1 ^ direction) = y;
    tree[y].parent = x;
    
    refresh_size(y);
    refresh_size(x);
}

注：上記コードは回転のロジックを示しています。
実際の実装ではポインタまたは配列インデックスを用いて双方向リンクを更新する必要があります。

Splay 操作の定義

Splay 操作は、指定されたノードを目標ノードの直下まで移動させるプロセスです。通常、ルートを最終目標とし、これにより頻出するキーがルートに近い位置に維持されます。

void splay_move(int target, int goal_node) {
    while (tree[target].parent != goal_node) {
        int p = tree[target].parent;
        int g = tree[p].parent;
        
        if (g != goal_node) {
            bool p_is_left = (tree[g].right == p);
            bool t_is_left = (tree[p].right == target);
            
            if (p_is_left != t_is_left) {
                perform_rotate(target);
            } else {
                perform_rotate(p);
            }
        }
        perform_rotate(target);
    }
    if (goal_node == 0) main_node = target;
}

標準的機能の実装

検索、挿入、削除、ランク取得などの機能は、Splay 操作を組み合わせることで実現されます。境界条件を防ぐために、最小値と最大値の仮定要素（Sentinel）を事前に登録しておくのが一般的です。

// ノードの追加
void insert_value(int v) {
    int curr = main_node;
    int prev = 0;
    
    while(curr && tree[curr].val != v) {
        prev = curr;
        curr = tree[curr].child(v > tree[curr].val);
    }
    
    if (curr) {
        tree[curr].count++;
    } else {
        tree[++nodes_count].parent = prev;
        tree[nodes_count].val = v;
        tree[nodes_count].count = 1;
        tree[nodes_count].size = 1;
        if(prev) {
            tree[prev].child(v > tree[prev].val) = nodes_count;
        }
        curr = nodes_count;
    }
    splay_move(curr, 0);
}

// ランクの取得
int get_rank_by_value(int v) {
    insert_value(v);
    return tree[tree[main_node].left].size;
}

// 第 k 番目の値を取得
int find_kth_element(int k) {
    int curr = main_node;
    while(true) {
        int l_sz = tree[tree[curr].left].size;
        if(k <= l_sz) {
            curr = tree[curr].left;
        } else if(k > l_sz + tree[curr].count) {
            k -= l_sz + tree[curr].count;
            curr = tree[curr].right;
        } else {
            return tree[curr].val;
        }
    }
}

// 除去処理
void delete_element(int v) {
    int la = get_predecessor(v);
    int ne = get_successor(v);
    
    splay_move(la, 0);
    splay_move(ne, la);
    
    int del_node = tree[ne].left;
    
    if(tree[del_node].count > 1) {
        tree[del_node].count--;
        splay_move(del_node, 0);
    } else {
        tree[ne].left = 0;
    }
}

前駆・後継ノードの探索は、単純な二分探索木としての走査 followed by splay 移動で行います。これは削除時に特定のノードを直接指すのではなく、その周辺の構造を使って安全に削除範囲を確定させるためです。

区間操作への拡張

スプレイ木は、配列の逆転や区間操作などにも応用可能です。この場合、ノードの値ではなく、その配置する「インデックス（位置）」をキーとして使用し、遅延ラグプロパゲーション（Lazy Tag）を追加することで区間変更を実現します。

例えば、範囲 [L, R] の反転操作を行う際は、まず L-1 番目の要素をルートにし、次いで R+1 番目の要素をその子の左側に移動させます。そうすると、対象となる区間全体が一つの左の子孫部分木として分離され、そのノードに「反転フラグ」を立てるだけで済みます。

struct LazyTreeNode {
    int left, right, parent;
    int index;
    bool flip_tag;
    int size;
};

void push_down(int u) {
    if(tree[u].flip_tag) {
        int l = tree[u].left;
        int r = tree[u].right;
        tree[l].flip_tag ^= 1;
        tree[r].flip_tag ^= 1;
        std::swap(tree[u].left, tree[u].right);
        tree[u].flip_tag = false;
    }
}

// セグメントツリー的な区間逆転
void reverse_interval(int l, int r) {
    // インデックスベースの座標変換を行う必要がある場合があるため、
    // ルートから k-th で必要なノードを特定します。
    
    int left_boundary = find_index(l); 
    int right_boundary = find_index(r);
    
    splay_move(left_boundary, 0);
    splay_move(right_boundary, left_boundary);
    
    tree[tree[right_boundary].left].flip_tag ^= 1;
}

このアプローチにより、O(log N) での部分配列操作が可能になります。

K 番目要素の検索修正

遅延タグを持つ状態では、再帰的に走査する前に必ず子ノードに対して push_down を実行する必要があります。

int query_kth_with_lazy(int k) {
    int curr = main_node;
    while(true) {
        push_down(curr);
        int l_sz = tree[tree[curr].left].size;
        if(k <= l_sz) {
            curr = tree[curr].left;
        } else if(k > l_sz + tree[curr].count) {
            k -= l_sz + tree[curr].count;
            curr = tree[curr].right;
        } else {
            return tree[curr].index;
        }
    }
}