Segment Tree (Part 1)

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

Operations of Segment Tree:
Operation Complexity Description
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
Implementation:

Before going to code it's inevitable to discuss theory behind segment tree. Segment tree is a binary tree in which:

  1. Leaf node represents exact elements of the input array.
  2. 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:

Blog Comments powered by Disqus.

Next Post Previous Post