Lessons - Amortized Preprocessing

This problem shows the power of amortized preprocessing. Spending $O(n \log n)$ time upfront lets you answer $q$ queries in $O(q \log n)$ total time. If you tried to answer each query by traversing the tree, you would spend $O(n)$ per query, making the total $O(qn)$.

For $q = 10^5$ and $n = 10^5$, that is $10^{10}$ operations, which times out. Preprocessing is the difference between passing and failing on large inputs.