segment tree in C++

In this tutorial, we will learn how a segment tree is used in C++ language and how to build a segment tree in C++.

A segment tree is a binary tree used for storing values in sequential order of segments of an array.

Example of a Segment Tree in C++

Let us understand the segment tree through a simple example.

Consider an array of size ‘N’ (N elements in a tree) of an array ‘A’ corresponding to the segment tree ‘T’.

  • The root node or the parent node of T represents the whole array as A[0: N-1]
  • Now the root must be divided into half of the root node or parent node of an array: A[0:(N-1)/2] and A[(0:(N-1)/2)+1)] respectively.
  • Each child node is divided as per the above formula.
  • The height of the segment tree is logN.
  • The time complexity is O(nlogn).
  • Therefore the total number of nodes in a segment tree can be of size either of 2N or 2N-1 nodes in a segment tree ‘T’.

Once the segment tree is built user can either do a query or an update of elements in an array:

update: it allows the users to update the value of a number in an array of user choice.

query: it allows the user to query any of the element in the array.

Let us write a simple c++ program to understand in a better way.

C++ program to build a segment tree:

#include <iostream>
using namespace std;
void buildTree(int* arr,int* tree,int start,int end,int treeNode){
    if(start==end){
        tree[treeNode]=arr[start];
        return;
        
    }
    int mid=(start+end)/2;
    buildTree(arr,tree,start,mid,2*treeNode);
    buildTree(arr,tree,mid+1,end,2*treeNode+1);
    tree[treeNode]=tree[2*treeNode]+tree[2*treeNode+1];
    
}
int main(void){
    
    int arr[]={11,23,33,4,5,6,72};//user can give any desired values
    int* tree=new int[12];
    buildTree(arr,tree,0,6,1);
    for(int i=0;i<14;i++){
        cout<<tree[i]<<endl;
    }
    
}
output:

154
71
83
34
37
11
72
11
23
33
4
5
6

You may also read:

Leave a Reply

Your email address will not be published.