Skip to content
Algorithm Atlas
Data StructuresAll categories
SpecializedSource checked

Persistent Segment Tree

Keeps previous segment tree versions by copying only nodes along update paths.

Explore relationshipsOpen constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Data Structures
Difficulty
Advanced
Family
Persistent Data Structure
Tier
Specialized
Status
Verified
Review
Source Checked
Sources
1
Formulas
1
Relationships
2
Code example
Ready
Visualization
Ready

Overview

A persistent segment tree supports range queries over historical versions while sharing unchanged subtrees between versions.

Core Concepts

path copyingversion rootrange querystructural sharing

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(log n)

Average

O(log n)

Worst

O(log n)

Space

O(log n) per update

When to Use

  • Use when fast lookup needs path copying.
  • Use when the input matches the assumptions behind persistent Data Structure.

When Not to Use

  • Avoid when the operation mix does not benefit from the structure's maintenance cost.
  • Avoid when a simpler algorithm gives the required result with less setup.

What It Does

  • Keeps previous segment tree versions by copying only nodes along update paths
  • Uses path copying and version root to guide the work.
  • Produces stored structure.

Use Cases

  • Fast lookup
  • Maintaining ordered data
  • Representing graphs or spatial data

Inputs

  • Items
  • Keys or indexes
  • Operations to support

Outputs

  • Stored structure
  • Query results
  • Updated state

Key Formulas (1)

Persistent update cost

newnodes = O(log n)
new_nodes = O(log n)

Only nodes on the root-to-leaf path need to be copied.

Pseudocode

  1. 1.Prepare the inputs and state needed for Persistent Segment Tree.
  2. 2.Apply the path copying step while the stopping condition has not been met.
  3. 3.Update intermediate state and discard invalid candidates.
  4. 4.Return stored structure.

Canonical Example

Input
Persistent Segment Tree input with a small representative case
Output
Stored structure
Explanation
Persistent Segment Tree applies path copying to produce stored structure.

Implementation Notes

  • Test insertion, deletion, lookup, and boundary cases separately.
  • Keep the path copying step separate enough to test independently.

Common Pitfalls

  • Ignoring update costs can make a structure look faster than it is in practice.
  • Forgetting to check edge cases can make Persistent Segment Tree look correct on only ideal inputs.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show the structure layout and how operations move through or update it.

Persistent Segment Tree mechanism walkthrough step 1 of 4suvwxt
Step 1 of 4: Prepare the inputs and state needed for Persistent Segment Tree.
data-structures-mechanism

Notes

Persistent Segment Tree should be used with the assumptions and tradeoffs of persistent Data Structure in mind.

Sources (1)

What each reference supports for this entry.

Making Data Structures Persistent

Paper

Reference for path-copying persistence used to preserve historical versions of segment-tree style structures.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Variant ofSegment Tree

Data Structures · Core

Persistent segment trees retain historical versions of segment tree updates.

Compare with this
Conceptual neighborsPersistent Union-Find

Data Structures · Specialized

Both use persistence techniques to query older versions of an evolving structure.

Compare with this

Relationships

View full relationship page
Variant ofSegment Tree

Persistent segment trees retain historical versions of segment tree updates.

Related Algorithms

Segment TreeFenwick TreeSparse Table

Tags

Data StructurePersistent Data StructureRange QueryTree