Segment Trees

Motivation: Given an array of N numbers, you need to support two operations. Operation 1: find-min(i, j) = return the minimum value in array[i … j]. Operation 2: update(i, v) = update the value at array[i] to v. Solve the problem for N <= 10^6, number of operations <= 10^6.

To solve the above problem, both the operations need to run in O(log N) time, but using an naive array gives O(N) run-time for operation 1 (and O(1) run-time for operation 2). So how do you solve the problem? Read on. :)

Video tutorial: This is a superb tutorial, giving the motivation, walking through example, and going step-by-step through the pseudocode.

Text tutorial: This tutorial provides more intuition and also covers Binary Indexed Trees. Also has lots of graphics which always helps. segtree.pdf

Another text tutorial and some extensions: This tutorial on Codeforces is superb: Efficient and easy segment trees.

1. The implementation is top-notch. Its refined and simplified, and every operation if 5 lines of C++ code.
2. It increases the complexity one step at a time. So its easy to understand each step. The tutorial has 2 main sections and more sub-sections. Unless you breeze through the first section, I’d recommend doing the second half on a later day after you have digested the first half.

Notes: I’m quite surprised by the high quality of tutorials I found (both video and text) for segment trees. However, each of the tutorials seem to be one-off, i.e. the author might have a couple of tutorials, but not a dozen tutorials, one for each and every algorithm. Thats where the magic of simply curating the best tutorials from the entire web comes to power!

Credits: Thanks to Nikhil Chandak for sharing the PDF tutorial.