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:

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: