Advanced Segment Tree Visualizer

What is a Segment Tree?

A segment tree is a data structure that allows efficient range queries and updates on an array. It can answer range sum, minimum, maximum, product, and other aggregate queries in O(log n) time.

What is Lazy Propagation?

Lazy propagation is an optimization technique for segment trees that allows for efficient range updates (e.g., adding a value to all elements within a range). Instead of updating all individual leaf nodes in the range, it "lazily" marks internal nodes with pending updates and pushes these updates down to children only when necessary (i.e., when querying or updating a segment that overlaps with the lazy node's range).

How to Use This Visualizer

1. Build Tree: Enter an array of numbers (comma-separated) and click "Build Tree"
2. Range Query: Enter a start and end index to query the sum/min/max/product in that range
3. Point Update: Change a value at a specific index and see the tree update
4. Range Update (Lazy): Add a value to all elements in a given range using lazy propagation.
5. Step-by-Step: Use the step-by-step mode to see how queries and updates work
6. Node Details: Click on any node to see its details

Keyboard Shortcuts

• Space: Next step (in step-by-step mode)
• B: Build tree
• Q: Run query
• U: Perform Point Update
• R: Perform Range Update (Lazy)