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 only update in a HAVE-TO situation.
In order to build SegmentTree, we need a Node structure to fill up the tree. A typical Node structure is like below:
private class Node {
int value; // value indicates the position in nodes[] array
int from; // from and to is the range of node
int to; // from and to is the range of node
int size; // range length of node
int min;
int sum;
/*When pendingVal is null, means no pendingVal. Otherwise it is the pending value.
Pending value is used to propagate node's children.
When update pending value, min and sum are both update too. */
Integer pendingVal;
}
There are several useful function for segment tree.
contains(from1, to1, from2, to2) // to tell is range1 includes range2 overlap(from1, to1, from2, to2) // return true too if contains update(from, to, value) // add value to element in range[from,…,to]
Pending value in Node structure is a important one for lazy propagation. When update or query a node for a range, if node contains the range, we just update or return value. If node is a leaf node, we return. Or if node overlap with range, then we should proceed to node’s children nodes. Before we proceed to children nodes, we need to propagate the children nodes by the pending value in node.
When we propagate the node on its children, we simply return if pending value is null. If pending value from parent node is not null, we update children’s pending value and update children’s sum/min. After propagate, we set pending value of parent node to null. In each status of a node, as long as a node has pending value, we should make sure the node’s sum/min value is already updated.
Let’s try a process for below case,
num[] = [1, 2, 3, 4, 5]
update(0, 2, 1); [2, 3, 4, 4, 5]
update(0, 2, 1); [3, 4, 5, 4, 5]
update(1, 1, 1); [3, 5, 5, 4, 5]
update(3, 4, 1); [3, 5, 5, 5, 6]
querySum(2, 3); return 10
The process is like below:
After the whole process, it should return result 10.
Segment tree has its advantage for range query in O(logN) time plus O(NlogN) storage. However, its disadvantage is that 1. We should preprocess to build segment tree in O(N) time. 2. Segment tree is a static tree, which means it is not allowed to add a new element or delete an element.
Check my code on github: link