Segment Tree Implementation in C

A Segment Tree is a powerful data structure used for answering range queries efficiently, such as sum, minimum, or maximum queries over a range of elements in an array. It allows both updates and queries to be performed in logarithmic time, making it useful for dynamic arrays where elements are frequently updated and queried.

Program Structure

This implementation of a Segment Tree in C will include the following components:

1. Functions to build the Segment Tree from a given array.
2. Functions to update the Segment Tree when an element in the array changes.
3. Functions to perform range queries, such as summing the values over a specified range.
4. A main function to demonstrate the usage of the Segment Tree for range queries and updates.

Code Implementation

#include <stdio.h>
#include <stdlib.h>

// Function to build the segment tree
void buildSegmentTree(int arr[], int segTree[], int start, int end, int node) {
    if (start == end) {
        // Leaf node will have a single element
        segTree[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        // Recursively build the segment tree
        buildSegmentTree(arr, segTree, start, mid, 2 * node + 1);
        buildSegmentTree(arr, segTree, mid + 1, end, 2 * node + 2);
        // Internal node will have the sum of both of its children
        segTree[node] = segTree[2 * node + 1] + segTree[2 * node + 2];
    }
}

// Function to update the segment tree
void updateSegmentTree(int segTree[], int start, int end, int index, int value, int node) {
    if (start == end) {
        // Leaf node
        segTree[node] = value;
    } else {
        int mid = (start + end) / 2;
        if (index <= mid) {
            // If index is in the left child, recurse on the left child
            updateSegmentTree(segTree, start, mid, index, value, 2 * node + 1);
        } else {
            // If index is in the right child, recurse on the right child
            updateSegmentTree(segTree, mid + 1, end, index, value, 2 * node + 2);
        }
        // Internal node will have the sum of both of its children
        segTree[node] = segTree[2 * node + 1] + segTree[2 * node + 2];
    }
}

// Function to get the sum over a range
int rangeQuery(int segTree[], int start, int end, int l, int r, int node) {
    if (r < start || l > end) {
        // If the range is completely outside the segment
        return 0;
    }
    if (l <= start && r >= end) {
        // If the range completely covers the segment
        return segTree[node];
    }
    // If the range partially covers the segment, split into two
    int mid = (start + end) / 2;
    int leftSum = rangeQuery(segTree, start, mid, l, r, 2 * node + 1);
    int rightSum = rangeQuery(segTree, mid + 1, end, l, r, 2 * node + 2);
    return leftSum + rightSum;
}

// Main function to demonstrate the usage of the Segment Tree
int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Allocate memory for the segment tree
    int *segTree = (int*)malloc(4 * n * sizeof(int));

    // Build the segment tree
    buildSegmentTree(arr, segTree, 0, n - 1, 0);

    // Output the sum of the range [1, 3]
    printf("Sum of range [1, 3]: %d\n", rangeQuery(segTree, 0, n - 1, 1, 3, 0));

    // Update the segment tree
    updateSegmentTree(segTree, 0, n - 1, 1, 10, 0);

    // Output the updated sum of the range [1, 3]
    printf("Updated sum of range [1, 3]: %d\n", rangeQuery(segTree, 0, n - 1, 1, 3, 0));

    // Free allocated memory
    free(segTree);

    return 0;
}

Explanation

The program implements a Segment Tree in C, a powerful data structure that efficiently handles range queries and updates in an array. The Segment Tree allows both update and query operations to be performed in O(log n) time, making it ideal for scenarios where the array is frequently updated and queried.

The key components of this implementation are as follows:

The buildSegmentTree() function constructs the Segment Tree from a given input array. The function recursively divides the array into segments and stores the sum of each segment at the corresponding node in the Segment Tree. The leaves of the tree represent the individual elements of the array, while the internal nodes store the sums of the segments.

The updateSegmentTree() function updates the Segment Tree when an element in the array changes. It modifies the corresponding leaf node and then recursively updates the internal nodes to reflect the new sums. This operation ensures that the tree remains consistent after the update.

The rangeQuery() function efficiently computes the sum over a specified range in the array. It checks whether the range completely, partially, or does not cover the current segment and accordingly either returns the stored sum, divides the query into two sub-ranges, or returns 0.

In the main() function, we demonstrate the Segment Tree’s functionality by constructing the tree for an array, performing a range sum query, updating an element in the array, and then performing the range sum query again to show the updated results.

This implementation of the Segment Tree allows efficient querying and updating of range sums, making it useful for tasks such as range queries, dynamic sum calculations, and other applications where efficient range operations are required.