Persistent Data Structures

Written by Johannes Kapfhammer.

Contents

Persistent Segment Trees
Persistent Ropes

A persistent data structure is a data structure that remembers it previous state for each modification. This allows to access any version of this data structure that interest us and execute a query on it.

Persistence is a technique that can be applied to most kinds of balanced trees, such as segment trees or treaps.

Persistent Segment Trees

Please read Advanced Segment Trees before continuing with this article.

Segment Tree is a data structure the can be turned into a persistent data structure efficiently (both in time and memory consumption). We want to avoid copying the complete tree before each modification, and we don’t want to loose the $O(\log n)$ time behavior for answering range queries.

In fact, any change request in the Segment Tree leads to a change in the data of only O(logn) vertices along the path starting from the root. So if we store the Segment Tree using pointers (i.e. a vertex stores pointers to the left and the right child vertices), then when performing the modification query, we simply need to create new vertices instead of changing the available vertices. Vertices that are not affected by the modification query can still be used by pointing the pointers to the old vertices. Thus for a modification query $O(\log n)$ new vertices will be created, including a new root vertex of the Segment Tree, and the entire previous version of the tree rooted at the old root vertex will remain unchanged.

Let’s give an example implementation for the simplest Segment Tree: when there is only a query asking for sums, and modification queries of single elements.

shared_ptr implementation (Expand)Copy

struct node;
using node_ptr = shared_ptr<const node>;
struct node : enable_shared_from_this<const node> {
  node_ptr l, r;
  int sum;

  node(int val) : l(), r(), sum(val) {}

  node(node_ptr l, node_ptr r) : l(move(l)), r(move(r)), sum(0) {
    if (this->l) sum += this->l->sum;
    if (this->r) sum += this->r->sum;
  }

  static node_ptr build(size_t n) {
    assert(n > 0);
    if (n==1) return make_shared<node>(0);
    return make_shared<node>(build(n/2), build(n-n/2));
  }

  int get_sum(int tree_l, int tree_r, int query_l, int query_r) const {
    if (query_r <= tree_l || tree_r <= query_l) return 0;
    if (query_l <= tree_l && tree_r <= query_r) return sum;
    int tree_m = (tree_l + tree_r)/2;
    return l->get_sum(tree_l, tree_m, query_l, query_r) +
           r->get_sum(tree_m, tree_r, query_l, query_r);
  }

  node_ptr update(int tree_l, int tree_r, int pos, int new_val) const {
    if (pos < tree_l || pos >= tree_r) return shared_from_this();
    if (tree_r - tree_l == 1) return make_shared<node>(new_val);
    int tree_m = (tree_l + tree_r)/2;
    return make_shared<node>(l->update(tree_l, tree_m, pos, new_val),
                             r->update(tree_m, tree_r, pos, new_val));
  }
};

raw pointer implementation (Expand)Copy

struct node {
  const node *l, *r;
  int sum;

  node(int val) : l(0), r(0), sum(val) {}

  node(const node *l, const node* r) : l(l), r(r), sum(0) {
    if (l) sum += l->sum;
    if (r) sum += r->sum;
  }

  static const node* build(size_t n) {
    if (n==1) return new node(0);
    return new node(build(n/2), build(n-n/2));
  }

  int get_sum(int tree_l, int tree_r, int query_l, int query_r) const {
    if (query_r <= tree_l || tree_r <= query_l) return 0;
    if (query_l <= tree_l && tree_r <= query_r) return sum;
    int tree_m = (tree_l + tree_r)/2;
    return l->get_sum(tree_l, tree_m, query_l, query_r) +
           r->get_sum(tree_m, tree_r, query_l, query_r);
  }

  const node *update(int tree_l, int tree_r, int pos, int new_val) const {
    if (pos < tree_l || pos >= tree_r) return this;
    if (tree_r - tree_l == 1) return new node(new_val);
    int tree_m = (tree_l + tree_r)/2;
    return new node(l->update(tree_l, tree_m, pos, new_val),
                    r->update(tree_m, tree_r, pos, new_val));
  }
};

Note that this works on any kind of segment tree, including lazy ones.

Practice tasks:

Persistent Ropes

Similarly to a segment tree, this technique can be also applied to treaps.

Practice task: AROPE2.