1.
Introduction
2.
What is a Segment Tree?
2.1.
Representation of Segment Trees
2.2.
Operations in Segment Trees
3.
Implementation
3.1.
Build()
3.2.
Update()
3.3.
Query()
4.
4.1.
What is a Segment Tree?
4.2.
What is the time complexity of insertion and query in a Segment Tree?
4.3.
What is the advantage of Fenwick tree over Segment tree?
4.4.
What is the disadvantage of the Fenwick tree over the Segment tree?
5.
Conclusion
Last Updated: Mar 27, 2024

# Introduction to Segment Trees

0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

## Introduction

This blog will discuss a problem based on a Segment Tree. A segment tree is an advanced data structure used to solve range-based queries. For example, finding the minimum in the subarray A[L, R] (also known as Range Minimum Query Problem) and finding the sum of all elements from index L to R in an array.

## What is a Segment Tree?

A Segment Tree is a binary tree used to store intervals or segments. In the Segment Tree, each node represents an interval. The height of the segment tree is Log2N, where N is the number of leaves in the tree.

### Representation of Segment Trees

Consider an array A[ ] of length N and a corresponding segment tree T.

1. Each leaf node contains an element A[i] of the input array where 0 <= i < N.

2. The root node represents the whole array A[0: N-1].

3. Internal represents merging of some leaf nodes i.e. some segment A[i: j] for 0 <= i < j < N.

4. An array is used to represent the segment tree T. T[0] represents a node that contains information about array A[0: N-1].

5. For a node in the segment tree at index i, the left child is at index 2*i, the right child is at index 2*i + 1, and the parent at index i/2.

### Operations in Segment Trees

Segment supports two operations.

1. Update: To update a particular element in the array A[ ] and reflect the corresponding changes in the associated segment tree T.

2. Query: To query over an interval or segment of array A[ ] and return the answer to our problem ( it may be minimum/maximum/summation etc.)

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Implementation

### Build()

We start building the segment tree from the root node and go down recursively. The root node represents the whole array. Then we divide the array range into two halves recursively. When only one element is left in the segment, it is considered a base case, and we update tree[node] as A[index].

When both left and right child are built, value of parent node is updated

(tree[parent] = tree[left] + tree[right]).

``````void build(int node, int start, int end){
if(start == end){
// Leaf node will have a single element
tree[node] = A[start];
return;
}

int mid = (start + end) / 2;
// Recurse on the left child
build(node << 1, start, mid);
// Recurse on the right child
build(node << 1 | 1, mid+1, end);
// Internal node will have the sum of both of its children
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
``````

### Update()

This function updates the value at a specific index in the array. It also updates the corresponding segment tree.

We search for a node that contains the element to update. It is done recursively by going left or right according to the position of idx.

When coming back from recursion value of nodes on the path is also updated.

``````void update(int node, int start, int end, int idx, int val){
// Base Case
if(start == end){
A[idx] += val;
tree[node] += val;
return;
}
int mid = (start + end) >> 1;

// If is idx is present in the left child, recurse on [start, mid]
if(start <= idx and idx <= mid){
update(node << 1, start, mid, idx, val);
}

// If is idx is present in the right child, recurse on [mid+1, start]
else{
update(node << 1 | 1, mid+1, end, idx, val);
}

// Parent node will be sum of left & right child.
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
``````

### Query()

Query function is usually called over a range (here ‘l’ to ‘r’). It returns the answer to the problem in a given range (maximum/minimum/summation etc.).

Three conditions are checked to query over a range.

i). If the range represented by the node is completely outside the given range: Simple return 0.

ii). If the range represented by the node is entirely inside the given range: Then we can simply return the value of this node and need not recurse further.

iii). If the range represented by the node is partially inside the given range, we further recurse to the right and left child of the current node. Finally, return the sum of both children.

``````int query(int node, int start, int end, int l, int r){

// Query range & node range are completely disjoint.
if(r < start || end < l) return 0;

// Complete overlap
if(l <= start and end <= r){
return tree[node];
}

// Some overlap.
int mid = (start + end) >> 1;

int p1 = query(node << 1, start, mid, l, r);
int p2 = query(node << 1 | 1, mid+1, end, l, r);
return (p1 + p2);
}
``````

You can use mentioned templates of Segment tree and Lazy Segment tree in competitive programming contests( SegtreeLazySegtree

### What is a Segment Tree?

A Segment tree is a data structure that stores information about array segments and allows efficient processing of range queries along with updates.

### What is the time complexity of insertion and query in a Segment Tree?

The time complexity of insertion and deletion in a Binary Indexed Tree containing N elements is O(logN).

### What is the advantage of Fenwick tree over Segment tree?

The main advantage of the Fenwick tree is that it requires less space, is relatively simple to implement, and has concise code.

### What is the disadvantage of the Fenwick tree over the Segment tree?

We can only use the Fenwick tree in queries where L=1. Therefore it cannot solve many problems.

## Conclusion

Cheers if you reached here!!

This article gave a simple introduction on the Segment tree. Segment tree-based problems are sometimes simple to implement, but finding an efficient approach remains difficult.

Check out this problem - Longest Subarray With Sum K

Yet learning never stops, and there is a lot more to learn. So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Learning!!

Live masterclass