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 > n1)
{
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, n1, 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 > n1  qs > qe)
{
printf("Invalid Input");
return 1;
}
return getSumUtil(st, 0, n1, 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, n1, 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;
}
CIn 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>
CThis 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; }
CThis 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)
CThis 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)
CThis 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)
CThis 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)
CThis 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)
CThis 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)
CThis function allocates memory for the segment tree and calls constructSTUtil()
to fill the allocated memory. It returns the constructed segment tree.
int main()
CThis 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)

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.

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

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

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
 Introduction to Data Structures in C
 Trees in C
 Advanced Data Structures: Binary Trees in C
 Advanced Data Structures: graphs in C
 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.