Introduction to Segment Trees

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];
}

You can also try this code with Online C++ Compiler

Run Code

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];
}

You can also try this code with Online C++ Compiler

Run Code

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 also try this code with Online C++ Compiler

Run Code

You can use mentioned templates of Segment tree and Lazy Segment tree in competitive programming contests( Segtree, LazySegtree ) 

Frequently Asked Questions

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!!