Introduction to Segment Trees

Anant Dhakad
Last Updated: May 13, 2022

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.)

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

FAQs

  1. 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.
     
  2. 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).
     
  3. 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.
     
  4. 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.

Key Takeaways

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.

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

Was this article helpful ?
0 upvotes