Segment Tree

Visual Representation of a Segment Tree

Before going into the theoretical aspects of segment trees, let's first understand them practically. In this section, we will see what a segment tree looks like.

Consider an array A = [1,2,1,8,7 ]
 

The segment tree for the above array is shown below:

• The root node is represented by A[0,n-1] which stores the sum of all the elements of the given array.
   
• Then the segment A[0,n-1] is divided into two halves, namely A[0,n/2] and A[n/2+1,n-1], and the sum of each half is computed and stored.
   
• Each of these two halves is further split into half, and the sum is computed and stored.
   
• This process continues until all the segments length becomes 1.
   
• So, at the first level, there is one node that is the root. In the second level, there are two nodes, third level four nodes,...until the number of nodes in a level becomes n.

All the leaf nodes represent the individual elements of the array. As you can see in the above segment tree, the highlighted sums are nothing but the element at that index.

Properties of Segment Tree

• The height of the segment tree is O(log n) because while moving from the root to the leaves at every level, the length of the segments is reduced by half.
   
• The total number of nodes involved in the segment tree is 4*n.
  The total number of levels is log n and starting from one node at the first level, the number of nodes gets doubled at every level. 
  So, total number of nodes = 1+2+4+8+....+2^(log n) = 2^(logn + 1) -1 < 4n.

Construction of Segment Tree

Let's first think about the structure of a node in a segment tree.

Every node in a segment tree must store the following information:

1. Range/Interval represented by the node
    
2. Information about the segment/interval ( it can be the sum of the range or any other information like minimum/maximum element in that range)
    
3. Pointers to left and right child
    

We will define a structure with all the data variables above.

The algorithm to build the segment tree(for range sum, i.e. each node stores the sum of an interval) is as follows:

1. Define the root of the segment tree.
    
2. We have array A and the start and end indices as L=0 and R=n-1.
    
3. Now, let’s define a recursive function build() which takes as parameters the given array, current root, start index L and end index R of the interval.
    
4. For the current root, initialize its interval with L and R values.
    
5. Check if L==R. If so, then it means it is a leaf node, so the sum value of the current node will be A[L], i.e. array element at index L.
    
6. If L is not equal to R, then call the build() function recursively for the left and right children of current. Then, initialize the sum value of the current node as the sum of its left and right children.

Let’s see the recursive code implementation in the next section.

C++ Implementation

/*C++ code to implement segment tree and demonstrate operations like
construction of segment tree,query sum*/

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    // store the sum of the interval
    int sum;
    // store the interval in a pair of integers
    pair<int, int> interval; /* L=interval.first and R=interval.second*/
    Node *left;              // points to left child
    Node *right;             // points to right child
};

void build(vector<int> array, Node *cur_node, int L, int R)
{

    cur_node->interval = make_pair(L, R);
    if (L == R)
    {
        // if current node is a leaf node
        cur_node->sum = array[L];
        cur_node->left = NULL;
        cur_node->right = NULL;
        return;
    }
    cur_node->left = new Node;
    cur_node->right = new Node;

    build(array, cur_node->left, L, (L + R) / 2);
    build(array, cur_node->right, (L + R) / 2 + 1, R);

    cur_node->sum = cur_node->left->sum + cur_node->right->sum;

    return;
}

// returns the sum in the range [start, end]
int query(vector<int> array, Node *cur_node, int start, int end)
{

    int L = cur_node->interval.first;
    int R = cur_node->interval.second;

    if (R < start || L > end)
    {
        return 0;
    }

    if (start <= L && end >= R)
    {
        return cur_node->sum;
    }

    int left_index = query(array, cur_node->left, start, end);
    int right_index = query(array, cur_node->right, start, end);

    return left_index + right_index;
}

// To clear allocated memory at end of program
void clearMem(Node *cur_node)
{
    int L = cur_node->interval.first;
    int R = cur_node->interval.second;

    if (L != R)
    {
        clearMem(cur_node->left);
        clearMem(cur_node->right);
    }
    delete cur_node;
}

int main()
{
    // define n and array
    int n = 5;
    vector<int> array = {1, 2, 1, 8, 7};

    Node *root = new Node();
    build(array, root, 0, n - 1);

    cout << "The sum in the interval [1, 3] is "
        << query(array, root, 1, 3) << '\n';

    cout << "The sum in the interval [1, 4] is "
        << query(array, root, 1, 4) << '\n';

    clearMem(root);
    return 0;
}

Output

The sum in the interval [1, 3] is 11
The sum in the interval [1, 4] is 18

Time Complexity

1. For tree construction
   O(n), where n is the size of the given array. In a segment tree, there is a total of 2n-1 nodes, and we initialize every node once to construct the tree. So, time complexity becomes O(2n-1) which is nothing but O(n).
    
2. For range sum query
   O(log n), because for every range, at most 4 nodes are examined at each level. Since the number of levels is O(log n), the time complexity is O(log n).

Space Complexity 

O(n), since there are 2n-1 nodes in the segment tree to store the information of the array segments, the space complexity is linear, i.e. O(n).

Read More - Time Complexity of Sorting Algorithms

Frequently Asked Questions

1. What are segment trees?
   A Segment Tree is a data structure that effectively allows answering range queries over an array while still being flexible enough to modify the array.
    
2. Where are segment trees used?
   Segment Tree is used in cases where there are multiple range queries on array and modifications of elements of the same array.
    
3. What are some of the applications of segment trees?
   Segment Trees can be used to solve Range Min/Max & Sum Queries, and Range Update Queries in O(log n) time.

Key Takeaways

In this article, we discussed very interesting and useful data structure segment trees.

We started with an application of segment trees, then saw its important properties followed by its implementation. 
You can check out this tutorial on Segment Trees to gain more clarity.

Recommended problems -

• Zig Zag Tree Traversal 
• Preorder Traversal
• Largest BST In Binary Tree
   

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!