# 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[]

- The root of our tree will represent the entire interval of data we are interested in, i.e, arr[0...n-1].
- 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].
- The internal nodes will represent the merged result of their child nodes.
- 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.

- Find the minimum number in range [l,r].
- 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 }

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions