Given a list of elements Segment Tree can find out any information of a segment/part of the list. As an example, given an array
[8, 7, 3, 9, 5, 1, 10] you are asked to find sum of elements between between 2nd and 5th element (index starts from 0, including boundary). Answer is
Operations of Segment Tree:
|build()||O(n)||Build segment tree first time from given array|
|query()||O(lg n)||Query given a start index and end index of the array|
|updateSingle()||O(lg n)||Update a single element in array and segment tree will be updated as well|
|updateRange()||O(n)||Update elements of the array by a given value|
|updateRangeLazy()||O(n)||Update elements of the array by a given value in lazy way|
|queryLazy()||O(lg n)||Query given a start index and end index of the array in lazy way|
Before going to code it's inevitable to discuss theory behind segment tree. Segment tree is a binary tree in which:
- Leaf node represents exact elements of the input array.
- Internal nodes represents merged result of the leaf nodes. This merged result depends on what are we going to find out or the problem statement. Example: In range minimum/maximum query (RMQ problem) problem, internal nodes keep value of minimum of its children. In range sum query (RSQ) problem, internal nodes keep value of sum of it's children.
Now it's time to see a demonstration of building segment for a RSQ (Range Sum Query) problem: