Home » Data Structure

Segment Trees | Data Structure

Here, we are going to learn about the segmentation trees in data structure: what is segmentation tree, why do we need it and how to make it? Submitted by Indrajeet Das, on October 27, 2018

What is a segment tree?

A segment tree is a full binary tree where each node represents an interval. A node may store one or more data members of an interval which can be queried later.

Why do we need Segment tree?

Many problems require that we give results based on query over a range or segment of available data. This can be the tedious and slow process, especially if the number of queries is large.

A segment tree lets us process such queries efficiently in logarithmic order of time.

How do we make a Segment tree?

Let the data be in array arr[]

1. The root of our tree will represent the entire interval of data we are interested in, i.e, arr[0...n-1].
2. Each leaf of the tree will represent a range consisting of just a single element. Thus the leaves represent arr[0], arr[1], arr[2] ... arr[n-1].
3. The internal nodes will represent the merged result of their child nodes.
4. Each of the children nodes could represent approximately half of the range represented by their parent.

Segment Tree generally contains three types of method: Build, Query, and Update.

Let’s take an example:

Problem: Range minimum query

You are given N numbers and Q queries. There are two types of queries.

1. Find the minimum number in range [l,r].
2. Update the element at i^th position of array to val.

Basic Approach:

We can find minimum element in O(N) and update the element in O(1). But if N or Q (query) is a very large number, it will be very slow.

But it can be solved in logarithmic time with segment trees.

• The root of the tree is at index 1
• The children then will be at 2*i and 2*i+1 index.

#include<iostream>

using namespace std;

int tree[400005]; // segment tree structure
int arr[100005];  // input tree

//Build

void build_tree(int node, int a, int b){
	//node represent the current node number
	// a,b represent the current node range
	//for leaf a == b
	if(a==b){
		//for single element minimum will be the element itself
		tree[node] = arr[a];
		return;
	}

	int mid = (a + b) >> 1; // middle element
	tree[node] =
	build_tree(node*2,a,mid)+    // call for left half
	build_tree(node*2+1,mid+1,b);//call for right half
}

//Query
int query_tree(int node, int a, int b, int i, int j){
	//i, j represents the range to be queried
	if(a > b || a > j || b < i){ return INT_MAX;} // out of range

	if(a>= i && b<=j){
		return tree[node];  //segment within range
	}

	int mid = a+ b >> 1;
	int q1 = query_tree(node*2,a,mid,i,j);    //left child query
	int q2 = query_tree(node*2+1,mid+1,b,i,j); // right child query

	return q1>q2?q2:q1;
}

void update_tree(int node, int a,int b, int i, int val){
	if(a>b||a>i||b<i){
		return;//Out of range
	}

	if(a==b){
		tree[node] = val;
		return;
	}

	int mid = (a+b) >> 1;

	tree[node] = update_tree(node*2,a,mid,i,val) +  // updating left child
	update_tree(node*2+1,mid+1,b,val); //updating right child
}