# 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