15. Static Trees

[@mihailstoian7237]

As an optimization for step 4 (lookup table), you can even shave another log, since in those chunks you only have to query at the margins (either a prefix query or a suffix one).

[@jeroenodb]

But what if you get handed a very small query in a block from position 2 to 0.5 log(n)-1? Then you don't have the answer stored in the lookup table and you cannot answer faster than walking from 2 to 0.5log(n)-1, which takes O(log(n)) time.

[@mihailstoian7237]

@@jeroenodb Right, I also figured that out some hours after having writed that :)

[@maristotero3352]

Thank you so much! It was uploaded 5 years ago but helped me with my struggles with LA very much!

[@PinkuDebNath]

Nice video! But I feel so stupid :| I lost track after LCA.

[@ipmankus]

Read on topcoder :) , this is an uneasy explanation for competitive programming

[@sheldonlai1650]

Can you open the automatic caption feature?