Persistent Data Structures

Persistent Segment Tree

Persistent segment trees are very similar to sparse segment trees in the sense that we store child pointers. The key differences are that we have multiple roots and every time we "update" a node, we actually create a new node in its place (hence persistence).

Persistent Array

Resources

Solution

1#include <bits/stdc++.h>
2typedef long long ll;
3using namespace std;
4
5struct Node {
6    ll val;
7    Node *l, *r;
8
9    Node(ll x) : val(x), l(nullptr), r(nullptr) {}
10    Node(Node *ll, Node *rr) {

Problems

A nice thing about persistent segment trees is that they can be used for online 2D static range sum queries in $\mathcal{O}(\log N)$ time (think about it like prefix sums).

Persistent Heap