Segment Tree - Range Queries with Lazy Updates

Explanation of the Segment Tree data structure. This has recently become quite popular for coding contests and interview questions. It is used to make range queries and updates.

The segment tree consists of a base array and it's ancestors. Each ancestor holds information to answer a query involving all of its descendants. This works only when the function at ancestor is an aggregate function like sum, max, min, xor etc...

Construction requires O(N) space and time complexity.
Queries can be answered in O(logN) time. Updates can be made lazily by storing the information at parent and propagating only when required. Hence, the complexity of an update is also O(logN).

We explain with the help of an example: Flipping coins. This question is ideal to understand about range query and update data structures.

Flipping Coins:
https://www.codechef.com/problems/FLIPCOIN/

Code for Flipping Coins:
https://www.codechef.com/viewsolution/12145491

Tutorial by Utkarsh Lath:
http://letuskode.blogspot.in/2013/01/segtrees.html

Видео Segment Tree - Range Queries with Lazy Updates канала Gaurav Sen