Segment tree

Segment tree data structure provides O(log n) time operations to process a range query and update and array value.

Segment trees support sum queries,minimum queries, and many other queries. more info here

Implementation

We will use bottom-up technique to construct the segment tree. It requires 2*N space. The steps are given below

  1. Decide which value each node in segment tree will store i.e. sum, max, min etc
  2. Create an array of size 2 * N where N is the number of items in original array
  3. Copy original array to the end of new array
  4. Construct the tree backwards, start at position N, pick left and right nodes for position and apply the function (sum, max etc)
  • The following diagram show segment tree for sum queries. Starting from bottom, nodes are picked and sum function is applied until we reach the root node which contains the sum of whole array.

Finding sum of a range

The sum of range can be found using following function, this can be modified to perform other operations like min or max.

int sum(int a, int b) {
    a += n; b += n;
    int s = 0;
    while (a <= b) {
        if (a%2 == 1) s += tree[a++];
        if (b%2 == 0) s += tree[b--];
        a /= 2; b /= 2;
    }
    return s;
}

The even and odd checks in the sum function are performing some adjustments for each node in the segment tree that corresponds to the range you want to sum.

If the left endpoint of the range is odd, then it means the corresponding node in the tree does not start at the beginning of the range, so you need to include the first value in the sum.

Similarly, if the right endpoint of the range is even, then it means the corresponding node in the tree does not end at the end of the range, so you need to exclude the last value from the sum.

This can be verified if you show the ranges that each node covers in the above tree. See the image below

Segment tree sample for example given above

top