Alex's Anthology of Algorithms Common Code for Contests in Concise C++
Data Structures / Range Queries in One Dimension

2.4.15 Implicit Treap

2-Data-Structures/2.4.15_Implicit_Treap.cpp

Maintain a dynamically-sized array using a balanced binary search tree while supporting both dynamic queries and updates of contiguous subarrays via the lazy propagation technique. A treap maintains a balanced binary tree structure by preserving the heap property on the randomly generated priority values of nodes, thereby making insertions and deletions run in $O(\log n)$ with high probability.

Array indices are implicit rather than stored as keys: subtree sizes determine each node's current position, so inserting or erasing a value does not require renumbering later elements. The internal split(t, left, right, i) operation separates the first i values from the rest, and merge() concatenates two such sequences. Range operations isolate their target with two splits, modify or inspect its root, and merge the three pieces back together.

The query operation is defined by an associative aggregate function combine(a, b). The default code below assumes a numerical array type, defining queries for the "min" of the target range. Another possible query operation is "sum", in which case combine(a, b) should return a + b.

Range updates are defined by apply_delta(v, d, len), which applies an update delta d to an aggregate summary v representing len array values, and by compose_deltas(old, d), which combines a pending older delta with a newer delta in that order. These functions do not support arbitrary combinations: applying a delta to a combined segment must be equivalent to applying it to each child segment and then combining the results, and composed deltas must be equivalent to performing their updates sequentially. The default code below defines range assignment. For range increment, compose_deltas(old, d) should return old + d; apply_delta(v, d, len) should return v + d for range-min/range-max queries, and v + d * len for range-sum queries.

Range reversal is also propagated lazily. Since combine() may be order-sensitive, each node stores the aggregate of its subtree in both forward and reverse order. Reversing a subtree then swaps its children and these two aggregates before marking its descendants for later reversal.

  • ImplicitTreap<T>(n = 0, v = T{}) constructs an array of size n with indices $[0, {\htmlClass{math-inline-code}{\texttt{n}}})$, with all values initialized to v.
  • ImplicitTreap<T>(lo, hi) constructs an array from the half-open iterator range $[{\htmlClass{math-inline-code}{\texttt{lo}}}, {\htmlClass{math-inline-code}{\texttt{hi}}})$.
  • size() returns the size of the array.
  • empty() returns whether the array is empty.
  • at(i) returns the value at index i.
  • query(lo, hi) returns the aggregate of the values at indices in $[{\htmlClass{math-inline-code}{\texttt{lo}}}, {\htmlClass{math-inline-code}{\texttt{hi}}}]$.
  • update(lo, hi, d) applies the delta d to every index in $[{\htmlClass{math-inline-code}{\texttt{lo}}}, {\htmlClass{math-inline-code}{\texttt{hi}}}]$.
  • update(i, d) applies the delta d to the single index i.
  • reverse(lo, hi) reverses the order of the values in $[{\htmlClass{math-inline-code}{\texttt{lo}}}, {\htmlClass{math-inline-code}{\texttt{hi}}}]$.
  • insert(i, v) inserts a new value v before index i, shifting later elements one position right.
  • erase(i) removes the element at index i, shifting later elements one position left.
  • push_back(v) appends a new value v to the end of the array.
  • pop_back() removes the last element of the array.

The query and update operations match those of the point- and range-update segment trees in this section; insert(), erase(), push_back(), and pop_back() are additionally analogous to those of std::vector (here, insert() and erase() take an index instead of an iterator).

Time Complexity
  • $O(n \log n)$ on average per call to both constructors, where $n$ is the size of the array.
  • $O(1)$ per call to size() and empty().
  • $O(\log n)$ on average per call to all other operations.
Space Complexity
  • $O(n)$ for storage of the array elements.
  • $O(1)$ auxiliary for size() and empty().
  • $O(\log n)$ auxiliary stack space for all other operations.

Implementation

#include <cassert>
#include <cstdint>
#include <random>
#include <utility>

template<typename T>
class ImplicitTreap {
  static T combine(const T &a, const T &b) { return a < b ? a : b; }
  static T apply_delta(const T &v, const T &d, int64_t len) { return d; }
  static T compose_deltas(const T &d1, const T &d2) { return d2; }

  struct Node {
    static uint32_t rand32() {
      static uint32_t x = std::random_device{}() | 1U;
      x ^= x << 13;
      x ^= x >> 17;
      x ^= x << 5;
      return x;
    }

    T value, subtree_value, reverse_value, delta;
    bool pending, reversed;
    int size;
    uint32_t priority;
    Node *left, *right;

    explicit Node(const T &v)
        : value(v),
          subtree_value(v),
          reverse_value(v),
          pending(false),
          reversed(false),
          size(1),
          priority(rand32()),
          left(nullptr),
          right(nullptr) {}
  } *root;

  static int size(Node *n) { return (n == nullptr) ? 0 : n->size; }

  static void update_value(Node *n) {
    if (n == nullptr) {
      return;
    }
    n->subtree_value = n->left != nullptr ? combine(n->left->subtree_value, n->value) : n->value;
    if (n->right != nullptr) {
      n->subtree_value = combine(n->subtree_value, n->right->subtree_value);
    }
    n->reverse_value = n->right != nullptr ? combine(n->right->reverse_value, n->value) : n->value;
    if (n->left != nullptr) {
      n->reverse_value = combine(n->reverse_value, n->left->reverse_value);
    }
    n->size = 1 + size(n->left) + size(n->right);
  }

  static void update_delta(Node *n, const T &d) {
    if (n != nullptr) {
      n->value = apply_delta(n->value, d, 1);
      n->subtree_value = apply_delta(n->subtree_value, d, n->size);
      n->reverse_value = apply_delta(n->reverse_value, d, n->size);
      n->delta = n->pending ? compose_deltas(n->delta, d) : d;
      n->pending = true;
    }
  }

  static void reverse_subtree(Node *n) {
    if (n != nullptr) {
      std::swap(n->left, n->right);
      std::swap(n->subtree_value, n->reverse_value);
      n->reversed = !n->reversed;
    }
  }

  static void push(Node *n) {
    if (n == nullptr) {
      return;
    }
    if (n->pending) {
      update_delta(n->left, n->delta);
      update_delta(n->right, n->delta);
      n->pending = false;
    }
    if (n->reversed) {
      reverse_subtree(n->left);
      reverse_subtree(n->right);
      n->reversed = false;
    }
  }

  static void merge(Node *&n, Node *left, Node *right) {
    push(left);
    push(right);
    if (left == nullptr) {
      n = right;
    } else if (right == nullptr) {
      n = left;
    } else if (left->priority < right->priority) {
      merge(left->right, left->right, right);
      n = left;
    } else {
      merge(right->left, left, right->left);
      n = right;
    }
    update_value(n);
  }

  static void split(Node *n, Node *&left, Node *&right, int i) {
    push(n);
    if (n == nullptr) {
      left = right = nullptr;
    } else if (i <= size(n->left)) {
      split(n->left, left, n->left, i);
      right = n;
    } else {
      split(n->right, n->right, right, i - size(n->left) - 1);
      left = n;
    }
    update_value(n);
  }

  static void insert(Node *&n, Node *new_node, int i) {
    push(n);
    if (n == nullptr) {
      n = new_node;
    } else if (new_node->priority < n->priority) {
      split(n, new_node->left, new_node->right, i);
      n = new_node;
    } else if (i <= size(n->left)) {
      insert(n->left, new_node, i);
    } else {
      insert(n->right, new_node, i - size(n->left) - 1);
    }
    update_value(n);
  }

  static void erase(Node *&n, int i) {
    assert(n != nullptr);
    push(n);
    if (i == size(n->left)) {
      Node *left = n->left, *right = n->right;
      delete n;
      merge(n, left, right);
    } else if (i < size(n->left)) {
      erase(n->left, i);
    } else {
      erase(n->right, i - size(n->left) - 1);
    }
    update_value(n);
  }

  static Node *select(Node *n, int i) {
    assert(n != nullptr);
    push(n);
    if (i < size(n->left)) {
      return select(n->left, i);
    }
    if (i > size(n->left)) {
      return select(n->right, i - size(n->left) - 1);
    }
    return n;
  }

  void clean_up(Node *&n) {
    if (n != nullptr) {
      clean_up(n->left);
      clean_up(n->right);
      delete n;
    }
  }

 public:
  explicit ImplicitTreap(int n = 0, const T &v = T{}) : root(nullptr) {
    assert(n >= 0);
    for (int i = 0; i < n; i++) {
      push_back(v);
    }
  }

  template<typename It>
  ImplicitTreap(It lo, It hi) : root(nullptr) {
    for (; lo != hi; ++lo) {
      push_back(*lo);
    }
  }

  ~ImplicitTreap() { clean_up(root); }
  ImplicitTreap(const ImplicitTreap &) = delete;
  ImplicitTreap &operator=(const ImplicitTreap &) = delete;
  int size() const { return size(root); }
  bool empty() const { return root == nullptr; }

  void insert(int i, const T &v) {
    assert(0 <= i && i <= size());
    insert(root, new Node(v), i);
  }

  void erase(int i) {
    assert(0 <= i && i < size());
    erase(root, i);
  }

  void push_back(const T &v) { insert(size(), v); }

  void pop_back() {
    assert(!empty());
    erase(size() - 1);
  }

  T at(int i) const {
    assert(0 <= i && i < size());
    return select(root, i)->value;
  }

  T query(int lo, int hi) {
    assert(0 <= lo && lo <= hi && hi < size());
    Node *l1, *r1, *l2, *r2, *t;
    split(root, l1, r1, hi + 1);
    split(l1, l2, r2, lo);
    T res = r2->subtree_value;
    merge(t, l2, r2);
    merge(root, t, r1);
    return res;
  }

  void update(int lo, int hi, const T &d) {
    assert(0 <= lo && lo <= hi && hi < size());
    Node *l1, *r1, *l2, *r2, *t;
    split(root, l1, r1, hi + 1);
    split(l1, l2, r2, lo);
    update_delta(r2, d);
    merge(t, l2, r2);
    merge(root, t, r1);
  }

  void update(int i, const T &d) { update(i, i, d); }

  void reverse(int lo, int hi) {
    assert(0 <= lo && lo <= hi && hi < size());
    Node *l1, *r1, *l2, *r2, *t;
    split(root, l1, r1, hi + 1);
    split(l1, l2, r2, lo);
    reverse_subtree(r2);
    merge(t, l2, r2);
    merge(root, t, r1);
  }
};

Example Usage

#include <cassert>
#include <vector>
using namespace std;

vector<int> values(ImplicitTreap<int> &t) {
  vector<int> result;
  for (int i = 0; i < t.size(); i++) {
    result.push_back(t.at(i));
  }
  return result;
}

int main() {
  vector<int> a{99, -2, 1, 8, 10};
  ImplicitTreap<int> t(a.begin(), a.end());

  // Append 11, then append and remove 12.
  t.push_back(11);
  t.push_back(12);
  t.pop_back();
  assert(t.size() == 6);
  assert(t.at(5) == 11);
  assert(t.query(0, t.size() - 1) == -2);
  assert((values(t) == vector<int>{99, -2, 1, 8, 10, 11}));

  // Replace the first value by inserting 90 before it and erasing the old 99.
  t.insert(0, 90);
  t.erase(1);
  assert(t.at(0) == 90);
  assert(t.at(1) == -2);
  assert((values(t) == vector<int>{90, -2, 1, 8, 10, 11}));

  // Assign 2 to the first two values.
  t.update(0, 1, 2);
  assert(t.at(0) == 2);
  assert(t.at(1) == 2);
  assert(t.query(0, t.size() - 1) == 1);
  assert((values(t) == vector<int>{2, 2, 1, 8, 10, 11}));

  // Reverse the middle range: {2, 2, 1, 8, 10, 11} becomes {2, 10, 8, 1, 2, 11}.
  t.reverse(1, 4);
  assert(t.at(0) == 2);
  assert(t.at(1) == 10);
  assert(t.at(4) == 2);
  assert(t.at(5) == 11);
  assert(t.query(0, t.size() - 1) == 1);
  assert((values(t) == vector<int>{2, 10, 8, 1, 2, 11}));
  return 0;
}
Back to top