segment tree in C++
By Yanamandra ValliIn 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