# 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;
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```