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

- Range Sum Query
- Range Minimum Query
- Range Maximum Query

## Other Ways[]

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.