Make delicious recipes!

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 rangelow to rangehigh.
If there are too many range queries expected, then log(N) order may be desirable. This can be achieved by using a 'Segment Tree'.
  1. A segment tree holds all the values in its leaves.
  2. Every non-leaf node stores the sum of a range.
  3. 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 nodek has children at node2k+1 and node2k+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]
(nodek has children at node2k+1 and node2k+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 ... 2k
   Since 2k = n, => k = log(n)
   Thus series sum =
   = 2k+1 - 1
   = 2log(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;
}





Like us on Facebook to remain in touch
with the latest in technology and tutorials!


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

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal