Treap with Lazy Propagation
(data-structure/bst/lazy_treap.hpp)

• View this file on GitHub
• Last update: 2024-01-08 11:43:39+09:00
• Include: #include "data-structure/bst/lazy_treap.hpp"

Description

遅延伝搬 treap は，区間更新が可能な treap である．扱える代数的構造は遅延伝搬セグメント木と同様なので，そちらを参照．遅延伝搬セグメント木が提供する操作に加えて挿入，削除，併合，分割，区間反転が可能である．

基本的には非可換のモノイドも扱えるが，reverse 操作をする場合は可換性が必要である．非可換も実装を少しいじれば扱えるがめんどくさいので実装していない．

空間計算量: $O(n)$

Operations

• static Treap join(Treap l, Treap r)
  • l と r を併合する
  • 時間計算量: $\mathrm{expected}\ O(\log n)$
• pair<Treap, Treap> split(int k)
  • $[0, k)$ と $[k, n)$ に分割する
  • 時間計算量: $\mathrm{expected}\ O(\log n)$
• void update(int l, int r, E x)
  • 区間 $[l, r)$ の値に $x$ を作用させる．
  • 時間計算量: $\mathrm{expected}\ O(\log n)$
• T fold(int l, int r)
  • 区間 $[l, r)$ の値を fold する
  • 時間計算量: $\mathrm{expected}\ O(\log n)$
• void reverse(int l, int r)
  • 区間 $[l, r)$ を反転する
  • 時間計算量: $\mathrm{expected}\ O(\log n)$
• void insert(int k, T x)
  • $k$ 番目に $x$ を挿入する
  • 時間計算量: $\mathrm{expected}\ O(\log n)$
• void erase(int k)
  • $k$ 番目の要素を削除する
  • 時間計算量: $\mathrm{expected}\ O(\log n)$
• void push_front(T x)
• void push_back(T x)
• void pop_front()
• void pop_back()
  • 先頭/末尾に $x$ を追加する/の要素を削除する
  • 時間計算量: $\mathrm{expected}\ O(\log n)$
• int size()
  • 要素数を返す
  • 時間計算量: $O(1)$
• bool empty()
  • 空か判定する
  • 時間計算量: $O(1)$

Note

本当はstd::unique_ptrを使いたいんだがなぜかGitHub上でめちゃくちゃ遅くなるので生ポインタを使っている．std::unique_ptrにしてコンパイルが通るような書き方はしているので生ポインタによる怖いことは起きないと思う．

Verified with

• test/yosupo/dynamic_sequence_range_affine_range_sum.treap.test.cpp

Code

#pragma once
#include <cassert>
#include <random>
#include <tuple>
#include <utility>

template <typename M, typename O,
          typename M::T (*act)(typename M::T, typename O::T)>
class LazyTreap {
    using T = M::T;
    using E = O::T;

   public:
    LazyTreap() = default;

    static LazyTreap join(LazyTreap l, LazyTreap r) {
        return LazyTreap(join(std::move(l.root), std::move(r.root)));
    }

    std::pair<LazyTreap, LazyTreap> split(int k) {
        assert(0 <= k && k <= size());
        auto p = split(std::move(root), k);
        return {LazyTreap(std::move(p.first)), LazyTreap(std::move(p.second))};
    }

    void update(int l, int r, const E& x) {
        assert(0 <= l && l < r && r <= size());
        node_ptr a, b, c;
        std::tie(a, b) = split(std::move(root), l);
        std::tie(b, c) = split(std::move(b), r - l);
        b->lazy = O::op(b->lazy, x);
        root = join(join(std::move(a), std::move(b)), std::move(c));
    }

    T fold(int l, int r) {
        assert(0 <= l && l < r && r <= size());
        node_ptr a, b, c;
        std::tie(a, b) = split(std::move(root), l);
        std::tie(b, c) = split(std::move(b), r - l);
        auto ret = b->sum;
        root = join(join(std::move(a), std::move(b)), std::move(c));
        return ret;
    }

    void reverse(int l, int r) {
        assert(0 <= l && l < r && r <= size());
        node_ptr a, b, c;
        std::tie(a, b) = split(std::move(root), l);
        std::tie(b, c) = split(std::move(b), r - l);
        b->rev ^= true;
        root = join(join(std::move(a), std::move(b)), std::move(c));
    }

    void insert(int k, const T& x) {
        auto s = split(std::move(root), k);
        root = join(join(std::move(s.first), new Node(x)), std::move(s.second));
    }

    void erase(int k) {
        auto p = split(std::move(root), k);
        auto q = split(std::move(p.second), 1);
        root = join(std::move(p.first), std::move(q.second));
    }

    void push_front(const T& x) { root = join(new Node(x), std::move(root)); }

    void push_back(const T& x) { root = join(std::move(root), new Node(x)); }

    void pop_front() { root = split(std::move(root), 1).second; }

    void pop_back() { root = split(std::move(root), size() - 1).first; }

    int size() const { return size(root); }

    bool empty() const { return size() == 0; }

   private:
    struct Node;
    using node_ptr = Node*;

    static unsigned int rand() {
        static std::random_device rd;
        static std::mt19937 rng(rd());
        return rng();
    }

    struct Node {
        node_ptr left, right;
        T val, sum;
        E lazy;
        unsigned int pri;
        int sz;
        bool rev;

        Node() : Node(M::id()) {}
        Node(const T& x)
            : left(nullptr),
              right(nullptr),
              val(x),
              sum(val),
              lazy(O::id()),
              pri(rand()),
              sz(1),
              rev(false) {}
    };

    node_ptr root = nullptr;

    explicit LazyTreap(node_ptr root) : root(std::move(root)) {}

    static int size(const node_ptr& t) { return t ? t->sz : 0; }

    static void recalc(const node_ptr& t) {
        if (!t) return;
        t->sz = size(t->left) + 1 + size(t->right);
        t->sum = t->val;
        if (t->left) t->sum = M::op(t->left->sum, t->sum);
        if (t->right) t->sum = M::op(t->sum, t->right->sum);
    }

    static void push(const node_ptr& t) {
        if (t->rev) {
            std::swap(t->left, t->right);
            if (t->left) t->left->rev ^= true;
            if (t->right) t->right->rev ^= true;
            t->rev = false;
        }
        if (t->lazy != O::id()) {
            t->val = act(t->val, t->lazy);
            if (t->left) {
                t->left->lazy = O::op(t->left->lazy, t->lazy);
                t->left->sum = act(t->left->sum, t->lazy);
            }
            if (t->right) {
                t->right->lazy = O::op(t->right->lazy, t->lazy);
                t->right->sum = act(t->right->sum, t->lazy);
            }
            t->lazy = O::id();
        }
        recalc(t);
    }

    static node_ptr join(node_ptr l, node_ptr r) {
        if (!l) return r;
        if (!r) return l;
        push(l);
        push(r);
        if (l->pri > r->pri) {
            l->right = join(std::move(l->right), std::move(r));
            recalc(l);
            return l;
        } else {
            r->left = join(std::move(l), std::move(r->left));
            recalc(r);
            return r;
        }
    }

    static std::pair<node_ptr, node_ptr> split(node_ptr t, int k) {
        if (!t) return {nullptr, nullptr};
        push(t);
        if (k <= size(t->left)) {
            auto s = split(std::move(t->left), k);
            t->left = std::move(s.second);
            recalc(t);
            return {std::move(s.first), std::move(t)};
        } else {
            auto s = split(std::move(t->right), k - size(t->left) - 1);
            t->right = std::move(s.first);
            recalc(t);
            return {std::move(t), std::move(s.second)};
        }
    }
};

#line 2 "data-structure/bst/lazy_treap.hpp"
#include <cassert>
#include <random>
#include <tuple>
#include <utility>

template <typename M, typename O,
          typename M::T (*act)(typename M::T, typename O::T)>
class LazyTreap {
    using T = M::T;
    using E = O::T;

   public:
    LazyTreap() = default;

    static LazyTreap join(LazyTreap l, LazyTreap r) {
        return LazyTreap(join(std::move(l.root), std::move(r.root)));
    }

    std::pair<LazyTreap, LazyTreap> split(int k) {
        assert(0 <= k && k <= size());
        auto p = split(std::move(root), k);
        return {LazyTreap(std::move(p.first)), LazyTreap(std::move(p.second))};
    }

    void update(int l, int r, const E& x) {
        assert(0 <= l && l < r && r <= size());
        node_ptr a, b, c;
        std::tie(a, b) = split(std::move(root), l);
        std::tie(b, c) = split(std::move(b), r - l);
        b->lazy = O::op(b->lazy, x);
        root = join(join(std::move(a), std::move(b)), std::move(c));
    }

    T fold(int l, int r) {
        assert(0 <= l && l < r && r <= size());
        node_ptr a, b, c;
        std::tie(a, b) = split(std::move(root), l);
        std::tie(b, c) = split(std::move(b), r - l);
        auto ret = b->sum;
        root = join(join(std::move(a), std::move(b)), std::move(c));
        return ret;
    }

    void reverse(int l, int r) {
        assert(0 <= l && l < r && r <= size());
        node_ptr a, b, c;
        std::tie(a, b) = split(std::move(root), l);
        std::tie(b, c) = split(std::move(b), r - l);
        b->rev ^= true;
        root = join(join(std::move(a), std::move(b)), std::move(c));
    }

    void insert(int k, const T& x) {
        auto s = split(std::move(root), k);
        root = join(join(std::move(s.first), new Node(x)), std::move(s.second));
    }

    void erase(int k) {
        auto p = split(std::move(root), k);
        auto q = split(std::move(p.second), 1);
        root = join(std::move(p.first), std::move(q.second));
    }

    void push_front(const T& x) { root = join(new Node(x), std::move(root)); }

    void push_back(const T& x) { root = join(std::move(root), new Node(x)); }

    void pop_front() { root = split(std::move(root), 1).second; }

    void pop_back() { root = split(std::move(root), size() - 1).first; }

    int size() const { return size(root); }

    bool empty() const { return size() == 0; }

   private:
    struct Node;
    using node_ptr = Node*;

    static unsigned int rand() {
        static std::random_device rd;
        static std::mt19937 rng(rd());
        return rng();
    }

    struct Node {
        node_ptr left, right;
        T val, sum;
        E lazy;
        unsigned int pri;
        int sz;
        bool rev;

        Node() : Node(M::id()) {}
        Node(const T& x)
            : left(nullptr),
              right(nullptr),
              val(x),
              sum(val),
              lazy(O::id()),
              pri(rand()),
              sz(1),
              rev(false) {}
    };

    node_ptr root = nullptr;

    explicit LazyTreap(node_ptr root) : root(std::move(root)) {}

    static int size(const node_ptr& t) { return t ? t->sz : 0; }

    static void recalc(const node_ptr& t) {
        if (!t) return;
        t->sz = size(t->left) + 1 + size(t->right);
        t->sum = t->val;
        if (t->left) t->sum = M::op(t->left->sum, t->sum);
        if (t->right) t->sum = M::op(t->sum, t->right->sum);
    }

    static void push(const node_ptr& t) {
        if (t->rev) {
            std::swap(t->left, t->right);
            if (t->left) t->left->rev ^= true;
            if (t->right) t->right->rev ^= true;
            t->rev = false;
        }
        if (t->lazy != O::id()) {
            t->val = act(t->val, t->lazy);
            if (t->left) {
                t->left->lazy = O::op(t->left->lazy, t->lazy);
                t->left->sum = act(t->left->sum, t->lazy);
            }
            if (t->right) {
                t->right->lazy = O::op(t->right->lazy, t->lazy);
                t->right->sum = act(t->right->sum, t->lazy);
            }
            t->lazy = O::id();
        }
        recalc(t);
    }

    static node_ptr join(node_ptr l, node_ptr r) {
        if (!l) return r;
        if (!r) return l;
        push(l);
        push(r);
        if (l->pri > r->pri) {
            l->right = join(std::move(l->right), std::move(r));
            recalc(l);
            return l;
        } else {
            r->left = join(std::move(l), std::move(r->left));
            recalc(r);
            return r;
        }
    }

    static std::pair<node_ptr, node_ptr> split(node_ptr t, int k) {
        if (!t) return {nullptr, nullptr};
        push(t);
        if (k <= size(t->left)) {
            auto s = split(std::move(t->left), k);
            t->left = std::move(s.second);
            recalc(t);
            return {std::move(s.first), std::move(t)};
        } else {
            auto s = split(std::move(t->right), k - size(t->left) - 1);
            t->right = std::move(s.first);
            recalc(t);
            return {std::move(t), std::move(s.second)};
        }
    }
};

Back to top page