PrevNext
Rare
 0/4

Persistent Data Structures

Authors: Andi Qu, Benjamin Qi

?

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).

Focus Problem – read through this problem before continuing!

Persistent Array

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

Resources

Resources
oml1111
Anudeep2011

not great formatting

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

Solution

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

C++

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct Node {
ll val;
Node *l, *r;
Node(ll x) : val(x), l(nullptr), r(nullptr) {}
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 O(logN)\mathcal{O}(\log N) time (think about it like prefix sums).

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

Persistent Heap

Resources
Benq
StatusSourceProblem NameDifficultyTags
DMOJVery Hard
YSVery Hard

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext