PrevNext
Rare
 0/2

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.

Feel free to file a request to complete this using the "Contact Us" button.

Resources

Resources
oml1111
Anudeep2011not great formatting

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

Solution

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

C++

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 O(logN)O(\log N) time (think about it like prefix sums).

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

Persistent Heap

Resources
Benq
StatusSourceProblem NameDifficultyTagsSolution
DMOJVery HardCheck DMOJ
YSVery HardView Solution

Module Progress:

Give Us Feedback on Persistent Data Structures!

PrevNext