04 Try it yourself Interactive

Build the tree, then watch a query prune whole subtrees

Two tabs, one array. Build fills the 15 nodes bottom-up so you can see where every stored number comes from — in that tab amber marks the two children currently being added and green marks the nodes already filled. Range query runs the descent: amber means the node straddles the range and has to split, green means it sits entirely inside and its value is taken whole, rose means it is outside and returns nothing. Grey nodes are never visited at all — that is the O(log n).

Build, bottom-up
8 leaves, then 7 parents
Exactly 8 whole numbers (0–99), and a range l, r inside 0–7.
the array · indigo = the slice this node owns · green = already counted
Press Next to begin. Each press moves one step.


      

        
At node–

        
Cells covered–

        
Nodes filled0

        
Additions0

      


      

      

        
        
        
        step 0 / 0