Lazy Segment Tree — Interactive Walkthrough

Range-max segment tree with lazy propagation. Lazy defers range updates — instead of pushing a change to every node immediately, it stores a pending value and propagates it only when a node is actually visited.

① Set a range → ② Run Query or Update → ③ Step through with ← → keys (or buttons)

Range Query — max over [l..r]

Range Update — max(tree[i], val) for i in [l..r]

Step 0 / 0

Array size

N = 8

Memory: tree[] and lazy[] (1-indexed)

Internal nodes [0..15] — [0] unused
tree[]
lazy[]
Leaf nodes [16..31]
tree[]
lazy[]

Code 


      
    


    

    

    

      
Steps

      
    
    
    

    
    
      
    Node Colors
    
      
     Current node
    
      
     Exact match
    
      
     Invalid range
    
      
     Partial — recurse
    
      
     Push lazy down
    
      
     Apply value (update)
    
      
     Pull up max (children)
    
      
     Active leaf — click to edit
    
    
    

    
    
      
    Shortcuts
    
      
    → ← Next / prev step
    
      
    + - Add / remove node
    
    
    

    
    
      
    Operation History
    
      
    • No operations yet.