Segment tree (Deals with range queries in log(N) time)

Problem: Given an array, find the sum of a given range in log(N) time

Solution: Finding sum in O(n) time is trivial - just loop from range_{low} to range_{high}.
If there are too many range queries expected, then log(N) order may be desirable. This can be achieved
by using a 'Segment Tree'.

A segment tree holds all the values in its leaves.

Every non-leaf node stores the sum of a range.

Root stores the sum of all the leaves.

Example:

Given the array [5, 9, 1, 3, 2, 4, 0]
Its segment tree will be:
0-6
/ \
/ (24) \
/ \
/ \
/ \
0-3 4-6
/(18)\ /(6)\
/ \ / \
/ \ / \
0-1 2-3 4-5 [0](14)(4)(6)
/ \ / \ / \
[5] [9] [1] [3] [2] [4]
Where blue items denote the sum stored in each node and
Red items denote the actual elements in the array.

An O(log N) algorithm to find the sum of a given range is as follows:

// Starting index of the given range (global variable)
int rangeStart;
// Ending index of the given range (global variable)
int rangeEnd;
/**
* tree : Array representation of the segment tree.
* Every node_{k} has children at node_{2k+1} and node_{2k+2}
* treeNodeIndex : Current tree-node's index in the array representation of the segment tree.
* currSegStart/End : Range of array-nodes whose sum is held by current segment tree-node.
*/
int getSumOfRange(int []tree, int treeNodeIndex, int currSegStart, int currSegEnd)
{
// If this node is inside the given range,
// then include its sum in the final sum
if (rangeStart <= currSegStart && currSegEnd <= rangeEnd)
return tree[treeNodeIndex];
// If segment of this node is outside the given range,
// do not include this node in the final sum
if (currSegEnd < rangeStart || rangeEnd < currSegStart)
return 0;
// If a part of this segment overlaps with the given range
int mid = (currSegStart + currSegEnd)/2;
return getSumOfRange(tree, 2*treeNodeIndex+1, currSegStart, mid) +
getSumOfRange(tree, 2*treeNodeIndex+2, mid+1, currSegEnd);
}

Sample execution for range 3 to 5

treeNodeIndex (level indented)

currSegStart

currSegEnd

rangeStart

rangeEnd

SumRetured ?

0

0

6

3

5

No

1

0

3

3

5

No

3

0

1

3

5

No

4

2

3

3

5

No

9

2

2

3

5

No

10

3

3

3

5

Yes, sum = tree[10] = 3

2

4

6

3

5

No

5

4

5

3

5

Yes, sum = tree[5] = 6

array: [5, 9, 1, 3, 2, 4, 0]
segment tree: [24 18 6 14 4 6 0 5 9 1 3 2 4]
(node_{k} has children at node_{2k+1} and node_{2k+2})
0-6
/ \
/ (24) \
/ \
/ \
/ \
0-3 4-6
/(18)\ /(6)\
/ \ / \
/ \ / \
0-1 2-3 4-5 [0](14)(4)(6)
/ \ / \ / \
[5] [9] [1] [3] [2] [4]
Blue items denote the sum stored in each node and
Red items denote the actual elements in the array.

Final sum for range 3 to 5 = sum of all the yes above = 3+6 = 9

Updating a segment tree

If an element needs to be updated, we look up its index in the array and update the entire corresponding leg in the
segment tree.
If a sum of range is required, then that range can be looked up in the segment tree using binary search which is O(logN).
Thus, we have improved the efficiency of finding range from O(N) to O(logN).
To do this, O(1) update time had to be sacrificed and it became O(log N) too.

Extra space required by segment tree:
Storage of leaves needs O(n) space.
Immediate parents of leaves need n/2 space and their parents need n/4 space.
So space required by a segment tree is:

= n + n/2 + n/4 .... 1
= 1 + 2 + 4 + 8 ... 2^{k}
Since 2^{k} = n, => k = log(n)
Thus series sum =
= 2^{k+1} - 1
= 2^{log(n)+1} - 1

Segment tree construction:

// Returns the value of segment tree at the given index
int fillSegmentTree(int arr[], int index, int start, int end, int []tree)
{
if (start == end)
{
tree[index] = arr[start];
return arr[start];
}
int mid = (start + end)/2;
// Recurse and store the sum of left and right children
tree[index] = fillSegmentTree(arr, index*2+1, start, mid, tree) +
fillSegmentTree(arr, index*2+2, mid+1, end, tree);
// Return the value of current index in segment tree
return tree[index];
}
int [] buildSegmentTree(int arr[], int n)
{
int x = (int)(ceil(log2(n)));
int treeSize = (int)Math.pow(2, x+1) - 1;
int []tree = new int[treeSize];
fillSegmentTree(arr, 0, 0, n-1, tree);
return tree;
}

Got a thought to share or found a bug in the code? We'd love to hear from you: