##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
(Pay once, query many)
This problem shows the power of amortized preprocessing. Spending time upfront lets you answer queries in total time. If you tried to answer each query by traversing the tree, you would spend per query, making the total .
For and , that is operations, which times out. Preprocessing is the difference between passing and failing on large inputs.
