Persistent Segment Tree
Keep every version of a segment tree by path-copying only the changed nodes.
Interactive visualization
Use the controls to connect the idea to concrete operations before diving into the full write-up.
idx 0
2
idx 1
5
idx 2
4
idx 3
7
Versions are first-class
Persistence means updates do not destroy old history. Each new root points to a mostly shared tree, which is why old answers stay available cheaply.
Family
Range queries
Static and dynamic range aggregates via indexed trees, segment trees, and precomputed tables.
Builds on
1 topic
Read these first if you want the surrounding context.
Unlocks
0 next topics
Use these follow-ups when you want to apply the current idea in a richer setting.
Learning paths
4
This topic appears in curated progressions so you can keep moving without guessing the next step.
Problem
Sometimes you do not want only the latest array state. You want to ask queries against older versions too.
Core idea
When a segment-tree update changes one leaf, only the nodes on that root-to-leaf path need new copies. Every untouched subtree can be shared with earlier versions.
So each update returns a new root, while old roots remain valid.
Why it matters
Persistence turns “history” into something queryable.
That enables:
- range queries on old versions
- k-th order statistics over prefix versions
- time-travel style offline solutions
Complexity
| Operation | Time | Extra space |
|---|---|---|
| One update creating a new version | ||
| One query on any version | - |
Key takeaways
- Persistent segment trees save history by path-copying, not by cloning the whole structure
- A version is just a root pointer into mostly shared nodes
- This is rare advanced range-query material, but it is one of the cleanest persistence examples in DSA
- Heavy-light decomposition sometimes pairs with persistence when tree queries also need historical versions
Practice problems
| Problem | Difficulty | Key idea |
|---|---|---|
| K-th Number references | 🔴 Hard | Prefix versions plus order statistics |
| MKTHNUM | 🔴 Hard | Classic persistent segment tree problem |
| Persistent segment tree references | 🔴 Hard | Path copying and version roots |
Relation to other topics
- Segment Tree is the non-persistent base structure
- Heavy-Light Decomposition can use segment trees on tree paths, and persistence can extend that story further
- Mo’s Algorithm is another advanced answer when offline query structure matters more than online updates
Build on these first
These topics supply the mental model or underlying structure that this page assumes.
Related directions
These topics live nearby conceptually, even if they are not direct prerequisites.
DSU Rollback
Add an undo stack to Union-Find so merges can be reversed during offline divide-and-conquer or time-travel style processing.
Euler Tour Technique
Flatten a rooted tree into an array so subtree problems become range problems. This is the bridge between trees and range-query structures.
Heavy-Light Decomposition
Break tree paths into O(log n) heavy-chain segments so path queries can ride on top of a segment tree instead of walking edge by edge.
Li Chao Tree
Maintain dynamic line insertion and min/max queries by storing line candidates in a segment tree over x-values.
More from Range queries
Stay in the same family when you want parallel variations of the same mental model.
Prefix Sum
Precompute cumulative totals so any range sum becomes one subtraction. Prefix sums are the first serious range-query idea everyone should know.
Difference Array
Apply many range updates in O(1) each, then rebuild the final values with one prefix pass. Difference arrays are the update-side twin of prefix sums.
Fenwick Tree (Binary Indexed Tree)
Maintain prefix sums with O(log n) updates and queries using one tiny bit trick. Fenwick trees are the lightest dynamic range-query structure worth knowing.
Li Chao Tree
Maintain dynamic line insertion and min/max queries by storing line candidates in a segment tree over x-values.
Paths that include this topic
Follow one of these sequences if you want a guided next step instead of open-ended browsing.
Range-query toolkit
Start with static prefix tricks, then move into offline, persistent, dynamic, and precomputed range-query structures.
Rooted tree queries
Flatten subtrees, jump through ancestors, and break tree paths into array segments instead of climbing naively.
Tree path queries
Build the full ladder from ancestor queries to heavy-light decomposition and historical segment trees.
Offline toolkit
See how reordering queries, rolling back state, and preserving versions can replace online complexity.
From the blog
Pair the atlas with recent writing from the rest of the site when you want a broader engineering perspective alongside the topic graph.