Rare
0/2
Persistent Data Structures
Authors: Andi Qu, Benjamin Qi
Prerequisites
?
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 | |||
Anudeep2011 | not 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++
#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.
Feel free to file a request to complete this using the "Contact Us" button.
Persistent Heap
Resources | |||
---|---|---|---|
Benq |
Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|
DMOJ | Very Hard | Check DMOJ | |||
YS | Very Hard | View Solution |