Lazy Reversible Randomized Binary Search Tree (data_structure/lazy_reversible_randomized_binary_search_tree.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2025-05-05 16:38:12+09:00
Include: #include "data_structure/lazy_reversible_randomized_binary_search_tree.hpp"

要素の挿入、削除、区間に対する更新（遅延伝播）、区間反転、区間集約を高速に行うことができるデータ構造です。ランダム化平衡二分探索木をベースに、遅延伝播と区間反転の機能を加えています。俗にいう、遅延伝搬反転可能乱択平衡二分探索木です。

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

T: 要素の型。
op: 要素の二項演算 (モノイド)。T op(T, T) の形式である必要があります。
e: モノイドの単位元を返す関数。T e() の形式である必要があります。
S: 遅延伝播させる作用素の型。
mapping: 要素に作用素を適用する関数。T mapping(S, T) の形式である必要があります。
composition: 作用素の合成を行う関数。S composition(S, S) の形式である必要があります。
id: 作用素の単位元を返す関数。S id() の形式である必要があります。

使い方

insert

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

説明

現在の木 ptr のインデックス k の位置に値 v を挿入します。

ptr: 操作対象の木のルートノードへのポインタ。
k: 挿入する位置のインデックス (0-indexed)。
v: 挿入する値。

計算量

$O(\log N)$ (期待値)

erase

void erase(nptr& ptr, int k)

説明

現在の木 ptr のインデックス k の要素を削除します。

ptr: 操作対象の木のルートノードへのポインタ。
k: 削除する要素のインデックス (0-indexed)。

計算量

$O(\log N)$ (期待値)

reverse

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

説明

現在の木 ptr の区間 [l, r) (半開区間) の要素の並びを反転させます。

ptr: 操作対象の木のルートノードへのポインタ。
l: 区間の開始インデックス (0-indexed)。
r: 区間の終了インデックス (0-indexed)。

計算量

$O(\log N)$ (期待値)

apply

void apply(nptr& ptr, int l, int r, S x)

説明

現在の木 ptr の区間 [l, r) (半開区間) の各要素に作用素 x を適用します。

ptr: 操作対象の木のルートノードへのポインタ。
l: 区間の開始インデックス (0-indexed)。
r: 区間の終了インデックス (0-indexed)。
x: 適用する作用素。

計算量

$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 の結果。

計算量

$O(\log N)$ (期待値)

Depends on

Randomized Binary Search Tree (data_structure/randomized_binary_search_tree.hpp)

Required by

test/dynamic_sequence_range_affine_range_sum.test.cpp

Code

#pragma once
#include <data_structure/randomized_binary_search_tree.hpp>

template <typename T, auto op, auto e, typename S, auto mapping, auto composition, auto id>
struct LazyReversibleRandomizedBinarySearchTree {
    struct node;
    using nptr = std::unique_ptr<node>;
    struct node {
        T v, r, p;
        S lz{id()};
        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->r : e(), ptr->v), ptr->left ? ptr->left->r : 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;
        }
        {
            if (ptr->left) {
                prop(ptr->left, ptr->lz);
            }
            if (ptr->right) {
                prop(ptr->right, ptr->lz);
            }
            ptr->lz = id();
        }
    }

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

    void prop(nptr& ptr, const S x) {
        if (!ptr) return;
        ptr->v = mapping(x, ptr->v);
        ptr->p = mapping(x, ptr->p);
        ptr->r = mapping(x, ptr->r);
        ptr->lz = composition(x, ptr->lz);
    }

    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, tmp] = split(std::move(ptr), k);
        auto [M, R] = split(std::move(tmp), 1);
        M.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));
    }

    void apply(nptr& ptr, int l, int r, S x) {
        auto [L, tmp] = split(std::move(ptr), l);
        auto [M, R] = split(std::move(tmp), r - l);
        prop(M, x);
        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/lazy_reversible_randomized_binary_search_tree.hpp"
#include <data_structure/randomized_binary_search_tree.hpp>

template <typename T, auto op, auto e, typename S, auto mapping, auto composition, auto id>
struct LazyReversibleRandomizedBinarySearchTree {
    struct node;
    using nptr = std::unique_ptr<node>;
    struct node {
        T v, r, p;
        S lz{id()};
        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->r : e(), ptr->v), ptr->left ? ptr->left->r : 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;
        }
        {
            if (ptr->left) {
                prop(ptr->left, ptr->lz);
            }
            if (ptr->right) {
                prop(ptr->right, ptr->lz);
            }
            ptr->lz = id();
        }
    }

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

    void prop(nptr& ptr, const S x) {
        if (!ptr) return;
        ptr->v = mapping(x, ptr->v);
        ptr->p = mapping(x, ptr->p);
        ptr->r = mapping(x, ptr->r);
        ptr->lz = composition(x, ptr->lz);
    }

    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, tmp] = split(std::move(ptr), k);
        auto [M, R] = split(std::move(tmp), 1);
        M.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));
    }

    void apply(nptr& ptr, int l, int r, S x) {
        auto [L, tmp] = split(std::move(ptr), l);
        auto [M, R] = split(std::move(tmp), r - l);
        prop(M, x);
        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;
    }
};