PrevNext
Rare
 0/3

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
Anudeep2011not 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 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 NameDifficultyTagsSolutionURL
DMOJVery HardCheck DMOJ
YSVery HardView Solution

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!

Give Us Feedback on Persistent Data Structures!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext