implicit_lazy_treap.hpp

SECTIONData Structure INCLUDEnoya/implicit_lazy_treap.hpp

Implicit randomized treap with reversible monoid products and lazy range actions. Each node stores both product orders, so reversing a range only swaps its children and its forward/backward aggregates. A pending action is composed at a subtree root and pushed only before structural changes, which keeps every sequence operation logarithmic in expectation.

Verified by dynamic_sequence_range_affine_range_sum.

在隐式 Treap 序列上增加区间懒操作和翻转；适合需要剪切、拼接并批量修改子段的动态序列。

Implementation

View on GitHub

SourceExpanded

#ifndef NOYA_IMPLICIT_LAZY_TREAP_HPP
#define NOYA_IMPLICIT_LAZY_TREAP_HPP 1

/// @complexity Time: Expected O(log n) per insertion, erasure, reversal,
/// range update, or range product.
/// Space: O(n) nodes and O(log n) expected recursion stack.

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

namespace noya {

/// @brief Implicit randomized treap with reversible monoid products and lazy
/// range actions. Each node stores both product orders, so reversing a range
/// only swaps its children and its forward/backward aggregates. A pending
/// action is composed at a subtree root and pushed only before structural
/// changes, which keeps every sequence operation logarithmic in expectation.
template <class S, class F, auto op, auto e, auto mapping, auto composition,
          auto id>
struct implicit_lazy_treap {
  struct node {
    S value;
    S forward;
    S backward;
    F lazy;
    std::uint64_t priority;
    int left = -1;
    int right = -1;
    int size = 1;
    bool reversed = false;
  };

  std::vector<node> nodes;
  int root = -1;

  implicit_lazy_treap() = default;
  explicit implicit_lazy_treap(const std::vector<S> &values) {
    nodes.reserve(values.size());
    for (const S &value : values) {
      root = merge(root, make_node(value));
    }
  }

  int size() const { return node_size(root); }
  bool empty() const { return root == -1; }
  void reserve(int capacity) { nodes.reserve(capacity); }

  void insert(int position, const S &value) {
    assert(0 <= position && position <= size());
    auto [left, right] = split(root, position);
    root = merge(merge(left, make_node(value)), right);
  }

  S erase(int position) {
    assert(0 <= position && position < size());
    auto [left, suffix] = split(root, position);
    auto [middle, right] = split(suffix, 1);
    push(middle);
    S result = nodes[middle].value;
    root = merge(left, right);
    return result;
  }

  void reverse(int left, int right) {
    check_range(left, right);
    auto [prefix, suffix] = split(root, left);
    auto [middle, tail] = split(suffix, right - left);
    apply_reverse(middle);
    root = merge(prefix, merge(middle, tail));
  }

  void apply(int left, int right, const F &action) {
    check_range(left, right);
    auto [prefix, suffix] = split(root, left);
    auto [middle, tail] = split(suffix, right - left);
    apply_action(middle, action);
    root = merge(prefix, merge(middle, tail));
  }

  S prod(int left, int right) {
    check_range(left, right);
    auto [prefix, suffix] = split(root, left);
    auto [middle, tail] = split(suffix, right - left);
    S result = aggregate(middle, false);
    root = merge(prefix, merge(middle, tail));
    return result;
  }

  std::vector<S> to_vector() {
    std::vector<S> result;
    result.reserve(size());
    auto visit = [&](auto &self, int current) -> void {
      if (current == -1) {
        return;
      }
      push(current);
      self(self, nodes[current].left);
      result.push_back(nodes[current].value);
      self(self, nodes[current].right);
    };
    visit(visit, root);
    return result;
  }

private:
  std::uint64_t priority_state = 0x243f6a8885a308d3ULL;

  int node_size(int current) const {
    return current == -1 ? 0 : nodes[current].size;
  }
  S aggregate(int current, bool backward) const {
    if (current == -1) {
      return e();
    }
    return backward ? nodes[current].backward : nodes[current].forward;
  }

  std::uint64_t next_priority() {
    std::uint64_t value = (priority_state += 0x9e3779b97f4a7c15ULL);
    value = (value ^ (value >> 30)) * 0xbf58476d1ce4e5b9ULL;
    value = (value ^ (value >> 27)) * 0x94d049bb133111ebULL;
    return value ^ (value >> 31);
  }

  int make_node(const S &value) {
    nodes.push_back(
        {value, value, value, id(), next_priority(), -1, -1, 1, false});
    return int(nodes.size()) - 1;
  }

  void apply_reverse(int current) {
    if (current == -1) {
      return;
    }
    std::swap(nodes[current].left, nodes[current].right);
    std::swap(nodes[current].forward, nodes[current].backward);
    nodes[current].reversed = !nodes[current].reversed;
  }

  void apply_action(int current, const F &action) {
    if (current == -1) {
      return;
    }
    nodes[current].value = mapping(action, nodes[current].value);
    nodes[current].forward = mapping(action, nodes[current].forward);
    nodes[current].backward = mapping(action, nodes[current].backward);
    nodes[current].lazy = composition(action, nodes[current].lazy);
  }

  void push(int current) {
    if (current == -1) {
      return;
    }
    if (nodes[current].reversed) {
      apply_reverse(nodes[current].left);
      apply_reverse(nodes[current].right);
      nodes[current].reversed = false;
    }
    apply_action(nodes[current].left, nodes[current].lazy);
    apply_action(nodes[current].right, nodes[current].lazy);
    nodes[current].lazy = id();
  }

  void pull(int current) {
    nodes[current].size =
        1 + node_size(nodes[current].left) + node_size(nodes[current].right);
    nodes[current].forward =
        op(op(aggregate(nodes[current].left, false), nodes[current].value),
           aggregate(nodes[current].right, false));
    nodes[current].backward =
        op(op(aggregate(nodes[current].right, true), nodes[current].value),
           aggregate(nodes[current].left, true));
  }

  std::pair<int, int> split(int current, int left_size) {
    if (current == -1) {
      return {-1, -1};
    }
    push(current);
    if (node_size(nodes[current].left) >= left_size) {
      auto [left, right] = split(nodes[current].left, left_size);
      nodes[current].left = right;
      pull(current);
      return {left, current};
    }
    auto [left, right] = split(nodes[current].right,
                               left_size - node_size(nodes[current].left) - 1);
    nodes[current].right = left;
    pull(current);
    return {current, right};
  }

  int merge(int left, int right) {
    if (left == -1 || right == -1) {
      return left == -1 ? right : left;
    }
    if (nodes[left].priority > nodes[right].priority) {
      push(left);
      nodes[left].right = merge(nodes[left].right, right);
      pull(left);
      return left;
    }
    push(right);
    nodes[right].left = merge(left, nodes[right].left);
    pull(right);
    return right;
  }

  void check_range(int left, int right) const {
    assert(0 <= left && left <= right && right <= size());
  }
};

} // namespace noya

#endif // NOYA_IMPLICIT_LAZY_TREAP_HPP

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

/// @complexity Time: Expected O(log n) per insertion, erasure, reversal,
/// range update, or range product.
/// Space: O(n) nodes and O(log n) expected recursion stack.

namespace noya {

/// @brief Implicit randomized treap with reversible monoid products and lazy
/// range actions. Each node stores both product orders, so reversing a range
/// only swaps its children and its forward/backward aggregates. A pending
/// action is composed at a subtree root and pushed only before structural
/// changes, which keeps every sequence operation logarithmic in expectation.
template <class S, class F, auto op, auto e, auto mapping, auto composition,
          auto id>
struct implicit_lazy_treap {
  struct node {
    S value;
    S forward;
    S backward;
    F lazy;
    std::uint64_t priority;
    int left = -1;
    int right = -1;
    int size = 1;
    bool reversed = false;
  };

  std::vector<node> nodes;
  int root = -1;

  implicit_lazy_treap() = default;
  explicit implicit_lazy_treap(const std::vector<S> &values) {
    nodes.reserve(values.size());
    for (const S &value : values) {
      root = merge(root, make_node(value));
    }
  }

  int size() const { return node_size(root); }
  bool empty() const { return root == -1; }
  void reserve(int capacity) { nodes.reserve(capacity); }

  void insert(int position, const S &value) {
    assert(0 <= position && position <= size());
    auto [left, right] = split(root, position);
    root = merge(merge(left, make_node(value)), right);
  }

  S erase(int position) {
    assert(0 <= position && position < size());
    auto [left, suffix] = split(root, position);
    auto [middle, right] = split(suffix, 1);
    push(middle);
    S result = nodes[middle].value;
    root = merge(left, right);
    return result;
  }

  void reverse(int left, int right) {
    check_range(left, right);
    auto [prefix, suffix] = split(root, left);
    auto [middle, tail] = split(suffix, right - left);
    apply_reverse(middle);
    root = merge(prefix, merge(middle, tail));
  }

  void apply(int left, int right, const F &action) {
    check_range(left, right);
    auto [prefix, suffix] = split(root, left);
    auto [middle, tail] = split(suffix, right - left);
    apply_action(middle, action);
    root = merge(prefix, merge(middle, tail));
  }

  S prod(int left, int right) {
    check_range(left, right);
    auto [prefix, suffix] = split(root, left);
    auto [middle, tail] = split(suffix, right - left);
    S result = aggregate(middle, false);
    root = merge(prefix, merge(middle, tail));
    return result;
  }

  std::vector<S> to_vector() {
    std::vector<S> result;
    result.reserve(size());
    auto visit = [&](auto &self, int current) -> void {
      if (current == -1) {
        return;
      }
      push(current);
      self(self, nodes[current].left);
      result.push_back(nodes[current].value);
      self(self, nodes[current].right);
    };
    visit(visit, root);
    return result;
  }

private:
  std::uint64_t priority_state = 0x243f6a8885a308d3ULL;

  int node_size(int current) const {
    return current == -1 ? 0 : nodes[current].size;
  }
  S aggregate(int current, bool backward) const {
    if (current == -1) {
      return e();
    }
    return backward ? nodes[current].backward : nodes[current].forward;
  }

  std::uint64_t next_priority() {
    std::uint64_t value = (priority_state += 0x9e3779b97f4a7c15ULL);
    value = (value ^ (value >> 30)) * 0xbf58476d1ce4e5b9ULL;
    value = (value ^ (value >> 27)) * 0x94d049bb133111ebULL;
    return value ^ (value >> 31);
  }

  int make_node(const S &value) {
    nodes.push_back(
        {value, value, value, id(), next_priority(), -1, -1, 1, false});
    return int(nodes.size()) - 1;
  }

  void apply_reverse(int current) {
    if (current == -1) {
      return;
    }
    std::swap(nodes[current].left, nodes[current].right);
    std::swap(nodes[current].forward, nodes[current].backward);
    nodes[current].reversed = !nodes[current].reversed;
  }

  void apply_action(int current, const F &action) {
    if (current == -1) {
      return;
    }
    nodes[current].value = mapping(action, nodes[current].value);
    nodes[current].forward = mapping(action, nodes[current].forward);
    nodes[current].backward = mapping(action, nodes[current].backward);
    nodes[current].lazy = composition(action, nodes[current].lazy);
  }

  void push(int current) {
    if (current == -1) {
      return;
    }
    if (nodes[current].reversed) {
      apply_reverse(nodes[current].left);
      apply_reverse(nodes[current].right);
      nodes[current].reversed = false;
    }
    apply_action(nodes[current].left, nodes[current].lazy);
    apply_action(nodes[current].right, nodes[current].lazy);
    nodes[current].lazy = id();
  }

  void pull(int current) {
    nodes[current].size =
        1 + node_size(nodes[current].left) + node_size(nodes[current].right);
    nodes[current].forward =
        op(op(aggregate(nodes[current].left, false), nodes[current].value),
           aggregate(nodes[current].right, false));
    nodes[current].backward =
        op(op(aggregate(nodes[current].right, true), nodes[current].value),
           aggregate(nodes[current].left, true));
  }

  std::pair<int, int> split(int current, int left_size) {
    if (current == -1) {
      return {-1, -1};
    }
    push(current);
    if (node_size(nodes[current].left) >= left_size) {
      auto [left, right] = split(nodes[current].left, left_size);
      nodes[current].left = right;
      pull(current);
      return {left, current};
    }
    auto [left, right] = split(nodes[current].right,
                               left_size - node_size(nodes[current].left) - 1);
    nodes[current].right = left;
    pull(current);
    return {current, right};
  }

  int merge(int left, int right) {
    if (left == -1 || right == -1) {
      return left == -1 ? right : left;
    }
    if (nodes[left].priority > nodes[right].priority) {
      push(left);
      nodes[left].right = merge(nodes[left].right, right);
      pull(left);
      return left;
    }
    push(right);
    nodes[right].left = merge(left, nodes[right].left);
    pull(right);
    return right;
  }

  void check_range(int left, int right) const {
    assert(0 <= left && left <= right && right <= size());
  }
};

} // namespace noya