Segment Trees - Part I

Contents:-

1. Introduction
2. Motivation behind segment trees
3. Methods in segment trees
   • build()
   • query()
   • update()

Introduction:-

A segment tree is a data structure which stores the information about the array intervals. This allows to answer the range queries over an array efficiently while still being flexible enough to allow single element modification or point updates in the array.

Motivation behind segment trees:-

Let us assume that we have an array a[0...n-1]. We need to perform two operations in our array.

1. Update an element at index 'i' with x
2. Find the sum of the array at range (l,r) both l and r being inclusive and l<r.

Approach 1:- Naive Approach

In the naive approach the updation of array element at index i is performed in O(1) time.

a[i]=x

To calculate the sum at range (l,r) we need to traverse the array from l to r and add the value of the element to the result variable. This is a linear operation so the time complexity is O(n).

int res=0
for(int i=l; i<=r; i++) {
    res += a[i];
}

Let us suppose that we have n queries for the first operation and m queries for the second operation. The total time complexity would be:-

T(n) = n*O(1) + m*O(n) = O(n) + O(m*n)

If m is of the order of n, then the overall time complexity can be treated as T(n²).

Hence, it can be concluded that there is a trade-off between both the operations.

Approach 2:- Prefix sum array

Prefix sum technique uses an additional array pre[0...n-1] of the same size as the original array. The idea behind prefix sum array is that the pre[i] stores the sum of all the elements from index 0 to i in the original array, i.e.

pre[i] = a[0] + a[1] + ... + a[i]

To calculate the sum within a given range (l,r) we can use this prefix sum.

pre[r] stores the sum from 0 to r
pre[l-1] stores the sum from 0 to l-1
sum(l,r) = pre[r] - pre[l-1]

The sum is now calculated in O(1) time. So, for m queries we have O(m) time complexity.

But if the array is updated at index i, then the prefix sum will change from index i to n-1. So, there is a need to recompute the prefix sum with every point update. The time complexity in recomputing prefix sum is O(n). For m queries of point updates, the T.C. would be O(m*n). If m and n are of the same order then the T.C. is O(n²).

Hence, there is again a trade-off between both the operations.

Approach 3:- Using Segment Trees

A segment tree is a binary tree where the internal nodes represent an array segment and the leaf nodes represent our array elements. We use an array to implement segment tree.

Let us consider the array:- a={1, 7, 3, 6, 9} and T be the segment tree of array a where segment[0...i] represents the sum of array from index 0 to i.

We use divide and conquer approach to store values in our segment tree. The root node is indexed as 1 and represents segment [0...n-1]. The left child node of the root represents the segment [0, (n-1)/2] and right child node of the root represents segment [(n-1)/2 +1, n-1].

Generally, for a given node at index i which represents segment[l...r] :-

• its left child is at index 2*i and represents segment[l...(l+r)/2]
• its right child is at index 2*i+1 and represents segment[(l+r)/2 +1, r]

Look at the below illustration for more understanding:-

Methods in segment trees

Build operation:-

It is clear that the sum in the parent segment node at index i is the sum of left child segment node and right child segment node.

T[i] = T[2*i] + T[2*i+1],

which is equivalent to

segment[l...r] = segment[l, (l+r)/2] + segment[(l+r)/2 + 1, r]

where l and r are left and right bound of the parent segment
So, we use recursive calls to build our tree and since each vertex is visited once, the T.C. is O(n).

Query Operation:-

We have build the tree and let tl and tr be the left and right bound of the tree. Given left 'l' and right 'r' bound of a segment of the array, the objective is to calculate the sum in this range. We again use the recursive calls and check for the child nodes where the query range lie. If it is outside then return 0 or else if it completely overlaps with the parent node then return the parent node or else recursively call the child nodes.

Update Operation:-

The objective is to point update the array and rebuild the segment tree. We use recursive calls similar to build operation but we additionally pass idx and new_val to the function and when the leaf node index is equal to idx we update the value. And while returning from the recursive calls we update the parent node.

Implementation:-

#include <iostream>

using namespace std;

#define MAXN 100
int t[4*MAXN];


/*
 * Name:- build
 * Function:- Builds the segment tree based on the given array
 * Time Complexity:- O(n)--> size of the segment tree
 * Input:-
 *        a[]:- array for which segment tree is build
 *        v:- curr node of the segment tree
 *        l, r:- segment represented by index 'v'
 * Return Type:- void
 */
void build(int a[], int v, int l, int r) {
    // If the segment is a leaf node
    if(l==r) {
        t[v]=a[l];
        return;
    }
    // else t[v] = t[2*v] + t[2*v+1]
    build(a, 2*v, l, (l+r)/2);
    build(a, 2*v+1, (l+r)/2+1, r);
    t[v] = t[2*v] + t[2*v+1];
}

/*
 * Name:- query
 * Function:- returns the sum of the given range
 * Time Complexity:- O(log n) --> height of the tree
 * Input:-
 *        v:- curr node index
 *        tl, tr:- segment represented by curr node index 'v'
 *        l, r:- range in which the sum has to be calculated
 * Return :- returns the sum of the given range
 */
int query(int v, int tl, int tr, int l, int r) {
    if(l>r) return 0;
    // The query range equals the segment range
    if(l==tl && r==tr) return t[v];
    int t_mid = (tl+tr)/2;
    int ans = query(2*v, tl, t_mid, l, min(t_mid, r)) +
              query(2*v+1, t_mid+1, tr, max(t_mid+1, l), r);
    return ans;
}

/*
 * Name:- update
 * Function:- updates the element at given index and 
 *            rebuilds the segment tree
 * Time Complexity:- O(log n) --> height of the tree
 * Input:-
 *        v:- curr node index
 *        tl, tr:- segment represented by curr node index 'v'
 *        idx:- index of array to be updated
 *        val:- value
 * Return Type:- void
 */
void update(int v, int tl, int tr, int idx, int val) {
    // base condition
    if(tl==tr) {
        t[v] = val;
        return;
    }
    int t_mid = (tl+tr)/2;
    // process the child segments
    if(idx<=t_mid) update(2*v, tl, t_mid, idx, val);
    else update(2*v+1, t_mid+1, tr, idx, val);
    // process the current segment
    t[v] = t[2*v] + t[2*v+1];
}

int main() {
    int a[] = {2, 3, 7, 1, 8, 5, 4, 3, 9};
    int n = sizeof(a)/sizeof(a[0]);
    // Index of segment tree's root node starts from 1
    build(a, 1, 0, n-1);

    cout << query(1, 0, n-1, 1, 7) << " ";
    cout << query(1, 0, n-1, 2, 6) << " ";
    cout << query(1, 0, n-1, 7, 9) << " ";
    cout << query(1, 0, n-1, 4, 4) << " ";
    cout << query(1, 0, n-1, 4, 5) << " ";
    update(1, 0, n-1, 0, 0);

    cout << "\nAfter update\n";

    cout << query(1, 0, n-1, 1, 1);
    return 0;
}