Segment tree, lazy propagation
Segment tree is a very useful data structure which can give answer for range problem in O(logN) time once we have pre-built the tree. Such as sum, min, max in range [i, j]. Lazy propagation is used to lazily update value in segment tree. We try not to update node value as much as possible. We… Read More »