Segment Tree in C
A Segment Tree is a data structure in C that helps us quickly perform operations (like finding the sum, minimum, or maximum) on a range of elements in an array. It’s like a tree that stores information about parts of the array in each node.
In this article, we will learn what are segement trees, how they work and how to implement them in C language.
Segment Trees in C
A Segment Tree is a data structure that stores information about a range of elements in its nodes. It is mostly used to handle range queries with updates in an efficient manner. For example, we can perform a range summation of an array between the range L to R while also modifying the array from range L to R all in log (N) time complexity
The tree is built recursively by dividing the array into segments until each segment represents a single element. This structure enables fast query and update operations with a time complexity of O (log n), making it a powerful tool in algorithm design and optimization.
Basic Operations on Segement Trees in C
The basic processes provided by segment trees can be outlined as the construction, query, and update.
S.No | Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|---|
| 1 | Building Tree | Creating the structure of the segment tree and initializing it. | O(n) | O(n) |
| 2 | Updating Tree | Changing the tree by updating the value in the array at a point or over an interval. | O(log n) | O(n) |
| 3 | Querying Tree | Running a range query on the array. | O(log n) | O(n) |
Implementation of Basic Operations
Algorithm of Build Segement Tree
Build_Segment_Tree(arr, tree, start, end, treeNode):
If start == end:
tree[treeNode] = arr[start]
Return
mid = (start + end) / 2
Build_Segment_Tree(arr, tree, start, mid, 2*treeNode)
Build_Segment_Tree(arr, tree, mid+1, end, 2*treeNode+1)
tree[treeNode] = tree[2*treeNode] + tree[2*treeNode+1]
Algorithm of Update
Update_Segment_Tree(arr, tree, start, end, treeNode, idx, value):
If start == end:
arr[idx] = value
tree[treeNode] = value
Return
mid = (start + end) / 2
If idx > mid:
Update_Segment_Tree(arr, tree, mid+1, end, 2*treeNode+1, idx, value)
Else:
Update_Segment_Tree(arr, tree, start, mid, 2*treeNode, idx, value)
tree[treeNode] = tree[2*treeNode] + tree[2*treeNode+1]
Algorithm of Query
Query_Segment_Tree(tree, start, end, treeNode, left, right):
If start > right or end < left: // No overlap
Return 0
If start >= left and end <= right: // Complete overlap
Return tree[treeNode]
mid = (start + end) / 2 // Partial overlap
ans1 = Query_Segment_Tree(tree, start, mid, 2*treeNode, left, right)
ans2 = Query_Segment_Tree(tree, mid+1, end, 2*treeNode+1, left, right)
Return ans1 + ans2
In the above:
arris the input array.treeis the segment tree.startandendare the start and end indices of the segment of the input array that the current node of the segment tree represents.treeNodeis the index of the current node in the segment tree.idxis the index of the element to be updated in the input array.valueis the new value to be updated.leftandrightare the range of the query.
C Program to Implement Segment Tree
// C program to demonstrate Segment Tree implementation
#include <stdio.h>
#define MAX_SIZE 1000
int segmentTree[MAX_SIZE];
// Function to build the segment tree
void buildSegmentTree(int arr[], int node, int start,
int end)
{
if (start == end) {
segmentTree[node] = arr[start];
return;
}
int mid = (start + end) / 2;
buildSegmentTree(arr, 2 * node, start, mid);
buildSegmentTree(arr, 2 * node + 1, mid + 1, end);
segmentTree[node]
= segmentTree[2 * node] + segmentTree[2 * node + 1];
}
// Function to query the segment tree
int query(int node, int start, int end, int l, int r)
{
if (r < start || end < l)
return 0;
if (l <= start && end <= r)
return segmentTree[node];
int mid = (start + end) / 2;
return query(2 * node, start, mid, l, r)
+ query(2 * node + 1, mid + 1, end, l, r);
}
// Function to update the segment tree
void update(int node, int start, int end, int idx, int val)
{
if (start == end) {
segmentTree[node] = val;
return;
}
int mid = (start + end) / 2;
if (idx <= mid)
update(2 * node, start, mid, idx, val);
else
update(2 * node + 1, mid + 1, end, idx, val);
segmentTree[node]
= segmentTree[2 * node] + segmentTree[2 * node + 1];
}
// Driver code
int main()
{
int arr[] = { 1, 3, 5, 7, 9, 11 };
int n = sizeof(arr) / sizeof(arr[0]);
buildSegmentTree(arr, 1, 0, n - 1);
printf("Sum of elements in range [1, 3] is %d\n",
query(1, 0, n - 1, 1, 3));
update(1, 0, n - 1, 2, 10);
printf("Sum of elements in range [1, 3] after update "
"is %d\n",
query(1, 0, n - 1, 1, 3));
return 0;
}
Output
Sum of elements in range [1, 3] is 15 Sum of elements in range [1, 3] after update is 20
Applications of Segment Trees
- Segment Trees are used to answer range queries like finding the minimum, maximum, sum, greatest common divisor, least common multiple, etc., in an array in logarithmic time.
- Segment Trees can handle updates and modifications in the data structure.
- Segment Trees can be used with a technique called Lazy Propagation to perform range updates in logarithmic time.
- Segment Trees are used to solve the Range Minimum Query problem, which aims to find the minimum element from a range in an array.
- Segment Trees can also solve the Range Maximum Query problem, which aims to find the maximum element from a range in an array.
- Segment Trees can be used to find the count of distinct elements in a range.
- Segment Trees can be used to find the K-th number in a sequence.
Conclusion
In summary, a Segment Tree is a versatile data structure that allows efficient querying and updating of intervals or segments of an array. It is particularly useful for problems involving range queries, such as finding the sum, minimum, maximum, or any other operation over a specific range of elements in an array.