New update is available. Click here to update.

Segment Tree

Yukti Kumari
Last Updated: May 13, 2022

Introduction

In this article, we will understand segment trees followed by its implementation to answer range sum queries.

It seems quite overwhelming when we stumble upon the topic segment trees for the first time. But you need not worry because, in this article, we will try to analyze the segment trees from scratch.

Before starting, let me give you a little motivation to study segment trees, and you will definitely appreciate how useful it is.

So, we have come across the problem to find the sum of consecutive elements in an array from some index i to index j many times. 

What is the time complexity of this process? 

O(N), isn’t it?

Quite simple as we know that in the worst case, the index i can be 0 and index j can be N-1( where N is the size of the array). So, to find the sum, you need to traverse the entire array. Hence it is O(N).

Now, let’s say we are given Q such queries with different values of indexes i and j. So, what would be the time complexity now?

It will be O(Q*N)

When the number of queries Q increases, the time complexity also increases. But with the use of segment trees, we can find the sum in O(log N) time.

What is a Segment Tree? 

A Segment tree is nothing but a data structure that allows us to answer range queries effectively and at the same time also provides flexibility to update the array. 

Now, why do we call it a segment tree? 

It consists of two words: segment and tree. Tree because it is a binary tree and segment denotes that each node in the tree contains information about a segment of an array(or any linear data structure).

What makes segment trees so preferable?

It requires only a linear amount of memory for its implementation. So,  along with optimizing time complexity, it is also space-efficient. Hence, this property makes it more useful.

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).

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.
 

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 CodeStudio now!

Was this article helpful ?
2 upvotes