A **segment tree** is a data structure used to store information about array segments and answer segment queries efficiently. There are two main operations performed on a segment tree:

1. **range(i, j)**: gives the sum of the array elements starting at index i and ending at index j.

2. **update(i, val)**: updates
the value at index i to the val in the original array and updates the segment tree accordingly.

Both range(i, j) and update(i, val) take $log(n)$ time, where *n* is the number of elements in the segment tree.

# Construction

A segment tree is usually represented in an array. The following illustration shows an array and its corresponding segment tree (represented as a tree and array).

# Update

The following illustration explains how a segment tree is updated. The segment tree is represented as a tree for better ​understanding:

# Range query

The following illustration goes over how range(i, j) works:

What is a segment tree?

A segment tree is a data structure used to store information about array segments and answer segment queries efficiently. There are two main operations performed on a segment tree:   range(i, j): gives the sum of the array elements starting at index i and ending at index j.   update(i, val): updates the value at index i to the val in the original array and updates the segment tree accordingly.   Both range(i, j) and update(i, val) take log(n)log(n)log(n) time, where n is the number of elements in the segment tree. Construction A segment tree is usually represented in an array. The following illustration shows an array and its corresponding segment tree (represented as a tree and array). 