Data Structure and Algorithm
Segment Tree Data Structure with Practical Examples Part 01
 Introduction
 Representation of Segment Tree
 Building Segment Tree
 Querying in Segment Tree
 Updating Segment Tree
 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 divideandconquer 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.
Let's query for sum in the range (2, 6) in the segment tree we have previously built.
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 stepbystep 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
 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.
 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.
 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.
 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.
 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.
 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.
Priority Queue Data Structure with Practical Examples
Introduction to Graph Data Structure with Practical Examples
All Tutorials in this playlist
Popular Tutorials
Categories

Artificial Intelligence (AI)
11

Bash Scripting
1

Bootstrap CSS
0

C Programming
14

C#
0

ChatGPT
1

Code Editor
2

Computer Engineering
3

CSS
28

Data Structure and Algorithm
18

Design Pattern in PHP
2

Design Patterns  Clean Code
1

EBook
1

Git Commands
1

HTML
19

Interview Prepration
2

Java Programming
0

JavaScript
12

Laravel PHP Framework
37

Mysql
1

Node JS
1

Online Business
0

PHP
28

Programming
8

Python
12

React Js
19

React Native
1

Redux
2

Rust Programming
15

Tailwind CSS
1

Typescript
10

Uncategorized
0

Vue JS
1

Windows Operating system
1

Woocommerce
1

WordPress Development
2
Tags
 Artificial Intelligence (AI)
 Bash Scripting
 Business
 C
 C Programming
 Csharp programming
 C++
 Code Editor
 Computer Engineering
 CSS
 Data Structure and Algorithm
 Database
 Design pattern
 Express JS
 git
 Git Commands
 github
 HTML
 Java
 JavaScript
 Laravel
 Mathematics
 MongoDB
 Mysql
 Node JS
 PHP
 Programming
 Python
 React Js
 Redux
 Rust Programming Language
 TypeScript
 Vue JS
 Windows terminal
 Woocommerce
 WordPress
 WordPress Plugin Development