Segment Tree in C - Sanfoundry

This is a C Program to implement segment tree. We have an array arr[0 . . . n-1]. We should be able to
1. Find the sum of elements from index l to r where 0 <= l <= r <= n-1 2. Change value of a specified element of the array arr[i] = x where 0 <= i <= n-1. A simple solution is to run a loop from l to r and calculate sum of elements in given range. To update a value, simply do arr[i] = x. The first operation takes O(n) time and second operation takes O(1) time. Here is source code of the C Program to Implement Segment Tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#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;
```
```
}
```
```
 
```

int getSumUtil(int *st, int ss, int se, int qs, int qe, int index) {

    // 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[index];
```
```
 
```

    // 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 * index + 1) + getSumUtil(st,

            mid + 1, se, qs, qe, 2 * index + 2);

```
}
```
```
 
```

void updateValueUtil(int *st, int ss, int se, int i, int diff, int index) {

    // 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[index] = st[index] + diff;
```
```
    if (se != ss) {
```
```
        int mid = getMid(ss, se);
```

        updateValueUtil(st, ss, mid, i, diff, 2 * index + 1);

        updateValueUtil(st, mid + 1, se, i, diff, 2 * index + 2);

```
    }
```
```
}
```
```
 
```

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

```
}
```
```
 
```

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

```
}
```
```
 
```

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];
```
```
}
```
```
 
```
```
int *constructST(int arr[], int n) {
```
```
    // Allocate memory for segment tree
```

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

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

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

Output:

$ gcc SegmentTree.c
$ ./a.out
 
Sum of values in given range = 15
Updated sum of values in given range = 22

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Perform Searching in a BST

» Next - C Program to Check if a Binary Tree is an AVL Tree or Not

Related Posts:

Recommended Articles: