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) |
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.