Lecture about range queries
May 19, 2026
I gave this lecture to finalists of the Luxembourgish olympiad in informatics.
We discuss range sum queries and range minimum queries, which are for instance used when calculating running averages of temperatures, or finding height minima in a landscape.
For the static version of the problem, where the underlying data does not change, we discuss range sums in the case of RSQ (range sum queries) and square root decomposition/divide and conquer for RMQ (range minimum queries).
For the dynamic case, we look at segment trees, which are a sort of generalisation of the static divide and conquer solution from earlier, but where the update operation is O(log n).
Finally, we look at an interesting application of RMQ which allows us to find the lowest common ancestor of two nodes u, v in a rooted tree, i.e. the node that is closest to the root on the unique path joining u and v.
You can find the slides here: Slides
The supporting C++ code and tex source code of the presentation can be found here: Supporting documents