Randomized Binary Search Tree (data_structure/randomized_binary_search_tree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-05-03 21:36:35+09:00
• Include: #include "data_structure/randomized_binary_search_tree.hpp"

ランダム化二分探索木（Randomized Binary Search Tree, RBST）は、暗黙的なキー（配列のようなインデックス）を用いて要素の挿入、削除、区間に対する操作（反転、集約値取得）を高速に行うことができるデータ構造です。遅延評価（Lazy Propagation）により区間反転をサポートしています。

テンプレートパラメータ:

• T: 要素の型。
• op: 二項演算 (モノイド)。T op(T, T) の形式である必要があります。
• e: モノイドの単位元を返す関数。T e() の形式である必要があります。

使い方

RandomizedBinarySearchTree はノードへのポインタ (nptr) を根として操作を行います。初期状態は nullptr です。

insert

void insert(nptr& ptr, int k, T v)

説明

根が ptr である木に対し、インデックス k の位置に値 v を挿入します。既存の要素は後方にシフトされます。

• ptr: 木の根への参照。操作後、根が変更される可能性があります。
• k: 挿入する位置のインデックス (0-indexed)。
• v: 挿入する値。

制約

$0 \le k \le N$ (Nは挿入前の要素数)

計算量

$O(\log N)$ (期待計算量)

erase

void erase(nptr& ptr, int k)

説明

根が ptr である木に対し、インデックス k の要素を削除します。後方の要素は前方にシフトされます。

• ptr: 木の根への参照。操作後、根が変更される可能性があります。
• k: 削除する要素のインデックス (0-indexed)。

制約

$0 \le k < N$ (Nは削除前の要素数)

計算量

$O(\log N)$ (期待計算量)

reverse

void reverse(nptr& ptr, int l, int r)

説明

根が ptr である木に対し、区間 [l, r) (半開区間) の要素の並びを反転します。

• ptr: 木の根への参照。操作後、根が変更される可能性があります。
• l: 反転する区間の開始インデックス (0-indexed)。
• r: 反転する区間の終了インデックス (0-indexed)。

制約

$0 \le l \le r \le N$ (Nは要素数)

計算量

$O(\log N)$ (期待計算量)

operator()

T operator()(nptr& ptr, int l, int r)

説明

根が ptr である木に対し、区間 [l, r) (半開区間) の要素に対する二項演算 op の結果を返します。

• ptr: 木の根への参照。操作後、根が変更される可能性があります。
• l: 集約値を取得する区間の開始インデックス (0-indexed)。
• r: 集約値を取得する区間の終了インデックス (0-indexed)。
• 戻り値: 区間 [l, r) の要素に対する op の結果。区間が空の場合は単位元 e() を返します。

制約

$0 \le l \le r \le N$ (Nは要素数)

計算量

$O(\log N)$ (期待計算量)

Required by

• Lazy Reversible Randomized Binary Search Tree (data_structure/lazy_reversible_randomized_binary_search_tree.hpp)
• test/dynamic_sequence_range_affine_range_sum.test.cpp

Verified with

• test/range_reverse_range_sum.test.cpp

Code

#pragma once
#include <memory>

template <typename T, auto op, auto e>
struct RandomizedBinarySearchTree {
    struct node;
    using nptr = std::unique_ptr<node>;
    struct node {
        T v, r, p;
        bool rev{false};
        int siz{1};
        nptr left{nullptr}, right{nullptr};
        node(T _v) : v(_v), r(_v), p(_v) {}
    };

    void update(nptr& ptr) {
        ptr->siz = size(ptr->left) + size(ptr->right) + 1;
        ptr->p = op(op(ptr->left ? ptr->left->p : e(), ptr->v), ptr->right ? ptr->right->p : e());
        ptr->r = op(op(ptr->right ? ptr->right->p : e(), ptr->v), ptr->left ? ptr->left->p : e());
    }

    static int size(const nptr& ptr) {
        return !ptr ? 0 : ptr->siz;
    }

    void push(nptr& ptr) {
        if (ptr->rev) {
            if (ptr->left) {
                toggle(ptr->left);
            }
            if (ptr->right) {
                toggle(ptr->right);
            }
            ptr->rev = false;
        }
    }

    void toggle(nptr& ptr) {
        if (!ptr) {
            return;
        }
        std::swap(ptr->left, ptr->right);
        std::swap(ptr->p, ptr->r);
        ptr->rev ^= true;
    }

    static inline int rng() {
        static int x = 123456789;
        static int y = 362436069;
        static int z = 521288629;
        static int w = 88675123;
        int t;
        t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }

    nptr merge(nptr l, nptr r) {
        if (!l || !r) return l ? std::move(l) : std::move(r);
        if (rng() % (size(l) + size(r)) < size(l)) {
            push(l);
            l->right = merge(std::move(l->right), std::move(r));
            update(l);
            return std::move(l);
        } else {
            push(r);
            r->left = merge(std::move(l), std::move(r->left));
            update(r);
            return std::move(r);
        }
    }

    std::pair<nptr, nptr> split(nptr ptr, int k) {
        if (!ptr) {
            return {nullptr, nullptr};
        }
        push(ptr);
        if (k <= size(ptr->left)) {
            auto [L, R] = split(std::move(ptr->left), k);
            ptr->left = std::move(R);
            update(ptr);
            return {std::move(L), std::move(ptr)};
        } else {
            auto [L, R] = split(std::move(ptr->right), k - size(ptr->left) - 1);
            ptr->right = std::move(L);
            update(ptr);
            return {std::move(ptr), std::move(R)};
        }
    }

    void insert(nptr& ptr, int k, T v) {
        auto [L, R] = split(std::move(ptr), k);
        nptr new_ptr = std::make_unique<node>(v);
        ptr = merge(merge(std::move(L), std::move(new_ptr)), std::move(R));
    }

    void erase(nptr& ptr, int k) {
        auto [L, M] = split(std::move(ptr), k);
        auto [D, R] = split(std::move(M), 1);
        D.reset();
        ptr = merge(std::move(L), std::move(R));
    }

    void reverse(nptr& ptr, int l, int r) {
        auto [L, tmp] = split(std::move(ptr), l);
        auto [M, R] = split(std::move(tmp), r - l);
        toggle(M);
        ptr = merge(merge(std::move(L), std::move(M)), std::move(R));
    }

    T operator()(nptr& ptr, int l, int r) {
        auto [L, tmp] = split(std::move(ptr), l);
        auto [M, R] = split(std::move(tmp), r - l);
        auto res = M ? M->p : e();
        ptr = merge(merge(std::move(L), std::move(M)), std::move(R));
        return res;
    }
};

#line 2 "data_structure/randomized_binary_search_tree.hpp"
#include <memory>

template <typename T, auto op, auto e>
struct RandomizedBinarySearchTree {
    struct node;
    using nptr = std::unique_ptr<node>;
    struct node {
        T v, r, p;
        bool rev{false};
        int siz{1};
        nptr left{nullptr}, right{nullptr};
        node(T _v) : v(_v), r(_v), p(_v) {}
    };

    void update(nptr& ptr) {
        ptr->siz = size(ptr->left) + size(ptr->right) + 1;
        ptr->p = op(op(ptr->left ? ptr->left->p : e(), ptr->v), ptr->right ? ptr->right->p : e());
        ptr->r = op(op(ptr->right ? ptr->right->p : e(), ptr->v), ptr->left ? ptr->left->p : e());
    }

    static int size(const nptr& ptr) {
        return !ptr ? 0 : ptr->siz;
    }

    void push(nptr& ptr) {
        if (ptr->rev) {
            if (ptr->left) {
                toggle(ptr->left);
            }
            if (ptr->right) {
                toggle(ptr->right);
            }
            ptr->rev = false;
        }
    }

    void toggle(nptr& ptr) {
        if (!ptr) {
            return;
        }
        std::swap(ptr->left, ptr->right);
        std::swap(ptr->p, ptr->r);
        ptr->rev ^= true;
    }

    static inline int rng() {
        static int x = 123456789;
        static int y = 362436069;
        static int z = 521288629;
        static int w = 88675123;
        int t;
        t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }

    nptr merge(nptr l, nptr r) {
        if (!l || !r) return l ? std::move(l) : std::move(r);
        if (rng() % (size(l) + size(r)) < size(l)) {
            push(l);
            l->right = merge(std::move(l->right), std::move(r));
            update(l);
            return std::move(l);
        } else {
            push(r);
            r->left = merge(std::move(l), std::move(r->left));
            update(r);
            return std::move(r);
        }
    }

    std::pair<nptr, nptr> split(nptr ptr, int k) {
        if (!ptr) {
            return {nullptr, nullptr};
        }
        push(ptr);
        if (k <= size(ptr->left)) {
            auto [L, R] = split(std::move(ptr->left), k);
            ptr->left = std::move(R);
            update(ptr);
            return {std::move(L), std::move(ptr)};
        } else {
            auto [L, R] = split(std::move(ptr->right), k - size(ptr->left) - 1);
            ptr->right = std::move(L);
            update(ptr);
            return {std::move(ptr), std::move(R)};
        }
    }

    void insert(nptr& ptr, int k, T v) {
        auto [L, R] = split(std::move(ptr), k);
        nptr new_ptr = std::make_unique<node>(v);
        ptr = merge(merge(std::move(L), std::move(new_ptr)), std::move(R));
    }

    void erase(nptr& ptr, int k) {
        auto [L, M] = split(std::move(ptr), k);
        auto [D, R] = split(std::move(M), 1);
        D.reset();
        ptr = merge(std::move(L), std::move(R));
    }

    void reverse(nptr& ptr, int l, int r) {
        auto [L, tmp] = split(std::move(ptr), l);
        auto [M, R] = split(std::move(tmp), r - l);
        toggle(M);
        ptr = merge(merge(std::move(L), std::move(M)), std::move(R));
    }

    T operator()(nptr& ptr, int l, int r) {
        auto [L, tmp] = split(std::move(ptr), l);
        auto [M, R] = split(std::move(tmp), r - l);
        auto res = M ? M->p : e();
        ptr = merge(merge(std::move(L), std::move(M)), std::move(R));
        return res;
    }
};

Back to top page