Rare

0/4

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

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 $\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 |

Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|

DMOJ | Very Hard | ||||||||

YS | Very 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!