Segment Trees[ Edit ]

**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.

- The implementation is top-notch. Its refined and simplified, and every operation if 5 lines of C++ code.
- 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.

Read more…(295 words)

Mark as completed

Part of lists:

Previous

Dynamic Programming on Trees (or Tree DP)

Next

[SUMSUM] Enjoy Sum with Operations

About the contributor:

Keshav DhandhaniaFormer TopCoder India rank #1, IOI medalist

100%

Loading…

Have a question? Ask here…

Post

Contributor

Keshav DhandhaniaFormer TopCoder India rank #1, IOI medalist

100%

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.