Segment Tree Implementation in C++

A Segment Tree is a data structure that allows efficient processing of range queries and updates on an array. It is particularly useful for answering queries like sum, minimum, maximum, or greatest common divisor (GCD) of elements within a given range. The Segment Tree provides O(log n) time complexity for both queries and updates.

Program Structure

The C++ implementation of a Segment Tree will include:

1. Segment Tree Array: Creating an array to represent the Segment Tree structure.
2. Build Operation: Constructing the Segment Tree from a given input array.
3. Range Query Operation: Implementing the function to answer range queries (e.g., sum of elements within a range).
4. Update Operation: Implementing the function to update an element in the array and propagate the changes in the tree.

Code Implementation

#include <iostream>
#include <vector>

class SegmentTree {
private:
    std::vector<int> tree;
    int n;

    // Function to build the Segment Tree
    void buildTree(const std::vector<int> &arr, int start, int end, int node) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            buildTree(arr, start, mid, 2 * node + 1);
            buildTree(arr, mid + 1, end, 2 * node + 2);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    // Function to perform range query
    int rangeQuery(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return 0; // Out of range
        }
        if (l <= start && end <= r) {
            return tree[node]; // Complete overlap
        }
        int mid = (start + end) / 2;
        int leftSum = rangeQuery(2 * node + 1, start, mid, l, r);
        int rightSum = rangeQuery(2 * node + 2, mid + 1, end, l, r);
        return leftSum + rightSum;
    }

    // Function to update an element in the Segment Tree
    void updateTree(int node, int start, int end, int idx, int value) {
        if (start == end) {
            tree[node] = value;
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                updateTree(2 * node + 1, start, mid, idx, value);
            } else {
                updateTree(2 * node + 2, mid + 1, end, idx, value);
            }
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

public:
    // Constructor to initialize the Segment Tree
    SegmentTree(const std::vector<int> &arr) {
        n = arr.size();
        tree.resize(4 * n);
        buildTree(arr, 0, n - 1, 0);
    }

    // Function to perform range query
    int rangeQuery(int l, int r) {
        return rangeQuery(0, 0, n - 1, l, r);
    }

    // Function to update an element
    void update(int idx, int value) {
        updateTree(0, 0, n - 1, idx, value);
    }
};

// Main function to demonstrate the Segment Tree operations
int main() {
    std::vector<int> data = {1, 3, 5, 7, 9, 11};
    SegmentTree segTree(data);

    std::cout << "Sum of elements in range [1, 3]: " << segTree.rangeQuery(1, 3) << std::endl;

    segTree.update(1, 10);
    std::cout << "After updating index 1 to 10:" << std::endl;

    std::cout << "Sum of elements in range [1, 3]: " << segTree.rangeQuery(1, 3) << std::endl;

    return 0;
}

Explanation

Segment Tree Array

The SegmentTree class contains a vector tree that represents the Segment Tree. The size of this vector is initialized to four times the size of the input array to accommodate the tree structure.

Build Operation

The buildTree() function constructs the Segment Tree from the given input array. It recursively divides the array into two halves and stores the sum (or other aggregation) of the segments in the corresponding nodes of the tree. The base case occurs when the segment contains a single element, which is directly stored in the tree.

Range Query Operation

The rangeQuery() function is used to answer range queries (e.g., sum of elements within a range). It handles three cases:

• No Overlap: The queried range does not overlap with the current segment, so it returns 0.
• Complete Overlap: The queried range completely covers the current segment, so it returns the value stored at the current node.
• Partial Overlap: The queried range partially overlaps with the current segment, so it recurses into both the left and right children to get the required sum.

Update Operation

The updateTree() function is used to update an element in the input array. It recursively finds the corresponding node in the tree and updates it, propagating the change upwards to ensure that all affected nodes are updated accordingly.

Conclusion

The Segment Tree is a powerful data structure for handling range queries and updates efficiently. It offers O(log n) time complexity for both operations, making it suitable for scenarios where frequent queries and updates are required. This C++ implementation covers the essential operations of the Segment Tree, including building, querying, and updating.