Advanced Data Structures: segment trees

Hello there, fellow coder! Are you ready to dive into the fascinating world of advanced data structures? If you’ve been working with basic data structures like arrays, linked lists, stacks, and queues, it’s time to level up your skills. This tutorial will guide you through some of the most complex and advanced data structures, making them easy to understand and fun to learn. So, let’s get started!

Understanding Advanced Data Structures

Advanced data structures are the building blocks of efficient software. They are essential components that help us store, organize, and manage data in a more efficient manner. These structures, such as trees, graphs, and heaps, are a step up from the basic data structures you may already be familiar with.

Segment Trees

A segment tree is a powerful data structure that allows you to perform operations on segments of an array. It’s like a binary tree, but with superpowers. Let’s take a look at a simple code example:

// C code for Segment Tree
#include <stdio.h>
#include <math.h>

// A utility function to get the middle index from corner indexes.
int getMid(int s, int e) { return s + (e -s)/2; }

/*  A recursive function to get the sum of values in given range
    of the array.  The following are parameters for this function.

  st    --> Pointer to segment tree
  si    --> Index of current node in the segment tree. Initially
            0 is passed as root is always at index 0
  ss & se  --> Starting and ending indexes of the segment represented
                by current node, i.e., st[si]
  qs & qe  --> Starting and ending indexes of query range */
int getSumUtil(int *st, int ss, int se, int qs, int qe, int si)
{
    // If segment of this node is a part of given range, then return
    // the sum of the segment
    if (qs <= ss && qe >= se)
        return st[si];

    // If segment of this node is outside the given range
    if (se < qs || ss > qe)
        return 0;

    // If a part of this segment overlaps with the given range
    int mid = getMid(ss, se);
    return getSumUtil(st, ss, mid, qs, qe, 2*si+1) +
           getSumUtil(st, mid+1, se, qs, qe, 2*si+2);
}

/* A recursive function to update the nodes which have the given 
   index in their range. The following are parameters
    st, si, ss and se are same as getSumUtil()
    i    --> index of the element to be updated. This index is 
             in the input array.
   diff --> Value to be added to all nodes which have i in range */
void updateValueUtil(int *st, int ss, int se, int i, int diff, int si)
{
    // Base Case: If the input index lies outside the range of 
    // this segment
    if (i < ss || i > se)
        return;

    // If the input index is in range of this node, then update 
    // the value of the node and its children
    st[si] = st[si] + diff;
    if (se != ss)
    {
        int mid = getMid(ss, se);
        updateValueUtil(st, ss, mid, i, diff, 2*si + 1);
        updateValueUtil(st, mid+1, se, i

, diff, 2*si + 2);
    }
}

// The function to update a value in input array and segment tree.
// It uses updateValueUtil() to update the value in segment tree
void updateValue(int arr[], int *st, int n, int i, int new_val)
{
    // Check for erroneous input index
    if (i < 0 || i > n-1)
    {
        printf("Invalid Input");
        return;
    }

    // Get the difference between new value and old value
    int diff = new_val - arr[i];

    // Update the value in array
    arr[i] = new_val;

    // Update the values of nodes in segment tree
    updateValueUtil(st, 0, n-1, i, diff, 0);
}

// Return sum of elements in range from index qs (query start)
// to qe (query end).  It mainly uses getSumUtil()
int getSum(int *st, int n, int qs, int qe)
{
    // Check for erroneous input values
    if (qs < 0 || qe > n-1 || qs > qe)
    {
        printf("Invalid Input");
        return -1;
    }

    return getSumUtil(st, 0, n-1, qs, qe, 0);
}

// A recursive function that constructs Segment Tree for array[ss..se].
// si is index of current node in segment tree st
int constructSTUtil(int arr[], int ss, int se, int *st, int si)
{
    // If there is one element in array, store it in current node of
    // segment tree and return
    if (ss == se)
    {
        st[si] = arr[ss];
        return arr[ss];
    }

    // If there are more than one elements, then recur for left and
    // right subtrees and store the sum of values in this node
    int mid = getMid(ss, se);
    st[si] =  constructSTUtil(arr, ss, mid, st, si*2+1) +
              constructSTUtil(arr, mid+1, se, st, si*2+2);
    return st[si];
}

/* Function to construct segment tree from given array. This function
   allocates memory for segment tree and calls constructSTUtil() to
   fill the allocated memory */
int *constructST(int arr[], int n)
{
    // Allocate memory for the segment tree

    //Height of segment tree
    int x = (int)(ceil(log2(n))); 

    //Maximum size of segment tree
    int max_size = 2*(int)pow(2, x) - 1; 

    int *st = new int[max_size];

    // Fill the allocated memory st
    constructSTUtil(arr, 0, n-1, st, 0);

    // Return the constructed segment tree
    return st;
}

// Driver program to test above functions
int main()
{
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = sizeof(arr)/sizeof(arr[0]);

    // Build segment tree from given array
    int *st = constructST(arr, n);

    // Print sum of values in array from index 1 to 3
    printf("Sum of values in given range = %d\n", 
            getSum(st, n, 1, 3));

    // Update: set arr[1] = 10 and update corresponding 
    // segment tree nodes
    updateValue(arr, st,

 n, 1, 10);

    // Find sum after the value is updated
    printf("Updated sum of values in given range = %d\n",
             getSum(st, n, 1, 3));
    return 0;
}
C

In this code, we first construct a segment tree from the given array. Then, we print the sum of values in the array from index 1 to 3. After that, we update the value at array index 1 to 10 and update the corresponding segment tree nodes. Finally, we find the sum after the value is updated.

Detailed Explanations of the Segment Tree Code

Absolutely, let’s break down the segment tree code example:

// C code for Segment Tree
#include <stdio.h>
#include <math.h>
C

This is the start of our program. We include the standard input/output library and the math library.

// A utility function to get the middle index from corner indexes.
int getMid(int s, int e) { return s + (e -s)/2; }
C

This function calculates the middle index of a segment. It’s used to divide the segment into two halves.

int getSumUtil(int *st, int ss, int se, int qs, int qe, int si)
C

This function is used to calculate the sum of a given range. It takes the segment tree, the start and end of the segment, the start and end of the query range, and the current index in the segment tree as arguments.

void updateValueUtil(int *st, int ss, int se, int i, int diff, int si)
C

This function is used to update the values in the segment tree when a value in the array is changed. It takes the segment tree, the start and end of the segment, the index of the changed element, the difference between the new and old values, and the current index in the segment tree as arguments.

void updateValue(int arr[], int *st, int n, int i, int new_val)
C

This function updates a value in the array and the corresponding values in the segment tree. It uses the updateValueUtil() function to update the values in the segment tree.

int getSum(int *st, int n, int qs, int qe)
C

This function returns the sum of elements in a given range. It uses the getSumUtil() function to get the sum.

int constructSTUtil(int arr[], int ss, int se, int *st, int si)
C

This function constructs the segment tree from the given array. It’s a recursive function that fills the segment tree with sums of segments of the array.

int *constructST(int arr[], int n)
C

This function allocates memory for the segment tree and calls constructSTUtil() to fill the allocated memory. It returns the constructed segment tree.

int main()
C

This is the main function where we test the above functions. We create an array, construct a segment tree from the array, print the sum of values in a given range, update a value in the array and the segment tree, and print the updated sum of values in the given range.

I hope this breakdown helps you understand the code better!

Wrapping Up

Advanced data structures are a crucial part of any programmer’s toolkit. They allow us to handle complex data in a more efficient and organized manner. While they may seem daunting at first, with practice and understanding, they can become second nature. So, keep coding, keep learning, and remember – every great coder started out just like you!

Frequently Asked Questions (FAQ)

  1. What are advanced data structures?

    Advanced data structures are more complex structures that allow for efficient data management and operations. They include structures like trees, graphs, heaps, and more.

  2. What are the 4 data structures?

    The four basic types of data structures are arrays, linked lists, stacks, and queues.

  3. What are the 5 types of data structures?

    The five types of data structures are arrays, linked lists, stacks, queues, and trees.

  4. Is Advanced data structures hard?

    Advanced data structures can be challenging to learn at first, but with practice and understanding, they can be mastered.

Related Tutorials

  1. Introduction to Data Structures in C
  2. Trees in C
  3. Advanced Data Structures: Binary Trees in C
  4. Advanced Data Structures: graphs in C
  5. Advanced Data Structures: Heaps in C

Dive into the world of advanced data structures with our comprehensive guide. This article focuses on segment trees with practical code examples and easy explanations.

Scroll to Top