Segment Tree Data Structure with Practical Examples Part 01

• Introduction
• Representation of Segment Tree
• Building Segment Tree
• Querying in Segment Tree
  • Time Complexity
• Updating Segment Tree
  • Time Complexity
• Applications of Segment Tree
• Run C Programming Online Compiler

¶Introduction

A segment tree is a powerful data structure used to efficiently handle queries and updates, particularly when these operations involve ranges of elements. Unlike simpler data structures like arrays, which can only handle range queries and updates in linear time, segment trees allow us to execute these operations in logarithmic time. This makes them particularly useful in problems involving frequent range queries and updates, such as finding the sum, minimum, maximum, or greatest common divisor over a range of elements in an array. Prerequisites for understanding segment trees include a good grasp of Trees, recursion, and the divide and conquer paradigm.

¶Representation of Segment Tree

A segment tree is a binary tree where each node corresponds to a segment (or range) of the array. The root of the tree represents the entire array, and each leaf node represents an individual element. Internal nodes represent the union of segments from their child nodes, allowing the segment tree to store aggregated information about any range of elements in the array. For instance, if the problem requires finding the sum over a range, each node will store the sum of a specific segment of the array. For the array [3, 5, 9, 11, 3, 0, 8, 4] we can build the following segment tree,

¶Building Segment Tree

Building a segment tree is a process that involves constructing a binary tree from an array, where each node represents a segment of the array. The construction is done using a divide-and-conquer approach,

• The array is recursively split into two halves. The midpoint of the array is used to divide the array into two segments — a left segment and a right segment.

• For each segment, a node is created in the tree. If the segment contains more than one element, the process continues recursively for each half until we reach segments containing a single element, which become the leaf nodes of the tree.

• The values from the leaf nodes are then combined to form their respective parent nodes. This is done by merging the information from the child nodes, such as summing their values if the tree is being used to sum ranges. This process continues upwards until the root node, which represents the entire array, is formed.

A segment tree requires at most 4n nodes due to its binary structure. The tree’s levels contain progressively more nodes:

• the first level has 1 node (the root)
• the second has 2 nodes
• the third has 4 nodes, and so on

doubling each time until reaching the number of leaves, n. The total number of nodes across all levels can be estimated by the sum

1 + 2 + 4 + ⋯ + 2 ^{(log n)} < 2 ^{(log n) + 1} <= 4n

The height of the segment tree is O(log n), since each step down from the root halves the segment size, ensuring efficient operations.

Implementation in C

#define MXN 200005

// Segment Tree array
int segTree[4 * MXN];

// Function to build the segment tree
void build(int *arr, int id, int left, int right) {
    // If the segment is a single element
    if (left == right) {
        segTree[id] = arr[left];
        return;
    }
    // Compute the mid point of the segment
    int mid = (left + right) / 2;
    // Recursively build the left and right segments
    build(arr, 2 * id, left, mid);
    build(arr, 2 * id + 1, mid + 1, right);
    // Set the value of the current node to the sum of its children
    segTree[id] = segTree[2 * id] + segTree[2 * id + 1];
}

¶Querying in Segment Tree

Querying a segment tree allows us to efficiently retrieve information about a specific range in the array, such as the sum or minimum of the elements in that range. The query operation works by breaking down the query range into segments that align with the nodes in the tree,

• If the segment represented by a node lies completely within the query range, the node’s value is returned.
• If the segment partially overlaps with the query range, the query is recursively passed down to both children.
• If the segment does not overlap with the query range, the query is ignored for that node.

Implementation in C

// Function to query the sum in the range [l, r]
int query(int id, int left, int right, int l, int r) {
    // If the query range is invalid
    if (l > r) {
        return 0; // Return 0 for sum queries if the range is invalid
    }
    // If the current segment is exactly the query range
    if (left == l && right == r) {
        return segTree[id];
    }
    // Compute the mid point of the segment
    int mid = (left + right) / 2;
    // Query the left and right children
    int leftSum = query(2 * id, left, mid, l, (r < mid ? r : mid));
    int rightSum = query(2 * id + 1, mid + 1, right, (l > mid + 1 ? l : mid + 1), r);
    // Return the sum of both ranges
    return leftSum + rightSum;
}

¶Time Complexity

The time complexity of a query operation in a segment tree is O(logn) . This logarithmic complexity arises because each query traverses from the root to the leaf nodes, and since the tree’s height is O(logn), the query operation is very efficient.

¶Updating Segment Tree

Updating a value in a segment tree involves modifying a specific element in the array and adjusting the segment tree to reflect this change. Here’s a step-by-step description of the update process,

• Start from the root of the segment tree and navigate to the leaf node that corresponds to the index of the element you want to update.
• Set the value of the leaf node (in the segment tree) to the new value provided.
• Move up the tree from the updated leaf node to the root.
• For each node on the path from the leaf to the root, update its value to reflect the changes made in its child nodes. Specifically, the value of each node is updated to be the sum of its two children.

Let’s update the value of the index 5 in the segment tree with value -3 we have previously built.

Implementation in C

// Function to update the value at a specific position
void update(int id, int left, int right, int pos, int val) {
    // If the segment is a single element
    if (left == right) {
        segTree[id] = val;
        return;
    }
    // Compute the mid point of the segment
    int mid = (left + right) / 2;
    // Update the left or right segment based on the position
    if (pos <= mid) {
        update(2 * id, left, mid, pos, val);
    } else {
        update(2 * id + 1, mid + 1, right, pos, val);
    }
    // Update the current node value to reflect changes in children
    segTree[id] = segTree[2 * id] + segTree[2 * id + 1];
}

¶Time Complexity

Each node along the path from the leaf to the root is updated, and there are O(log n) such nodes in a segment tree. Therefore, the total time complexity for the update operation is O(log n). The segment tree ensures that updates are efficiently propagated to maintain correct values across all segments, allowing queries and updates to be handled in logarithmic time.

¶Applications of Segment Tree

1. Range Queries and Range Update : Segment trees efficiently handle range queries (e.g., sum, min, max) and range updates (e.g., adding a value to all elements in a range) in logarithmic time.
2. Lazy Propagation : Lazy propagation is a technique used in segment trees to delay updates to segments until necessary. This approach ensures efficient range updates and queries by minimizing the number of operations performed immediately.
3. Database Management Systems : Segment trees are used in databases for efficient range queries and updates, such as summing or finding maximum values within specified date ranges. They enhance performance in handling large datasets with frequent updates.
4. Computer Graphics : In graphics, segment trees manage and query pixel data or textures efficiently. They support operations like applying filters or updating color information in specific regions of an image or grid.
5. Text Processing : Segment trees help in text processing by enabling efficient range queries and updates on text data, such as substring searches or frequency counts of words over specified ranges in a document.
6. Scheduling and Resource Management : Segment trees manage scheduling and resource allocation by allowing efficient querying and updating of resource availability over time. This is useful for tasks like scheduling jobs or allocating resources across different time intervals.

¶Run C Programming Online Compiler

To make your learning more effective, exercise the coding examples in the text editor below.

Run C programming online