Segment tree is a data structure which can efficiently answer dynamic range queries. Generally, there are three kinds of queries:

  1. Range Sum Query
  2. Range Minimum Query
  3. Range Maximum Query

Other Ways Edit

There are several ways to answer there queries. One of the trivial algorithms is to scan from the beginning index to end index and keep track of min/max/sum. This takes no extra space and O(n) time per query. When n is large, the algorithm maybe infeasible.

A segment tree can be used to answer these queries. A Segment Tree is a data structure for storing intervals or segments. It is a binary tree similar to a Heap, but usually not a complete binary tree. The root of the tree contains the full segment, from [0, N-1]. And for each segment [L, R], we split it into 2 segments: [L, (L+R)/2] and [(L+R)/2 + 1, R] until L=R. It takes O(n log n) time to build the segment tree. Once the tree is built, it takes O(log n) time to answer each query.

If the array A is static, there exists a DP solution which requires a one time pre-processing time O(n log n) and access time of O(1) per query.

A segment tree becomes useful if the array A is frequently updated. We can update the segment tree in O(log n) time for each query. The DP solution requires another O(log n) time to do the same.