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:
arr
is the input array.tree
is the segment tree.start
andend
are the start and end indices of the segment of the input array that the current node of the segment tree represents.treeNode
is the index of the current node in the segment tree.idx
is the index of the element to be updated in the input array.value
is the new value to be updated.left
andright
are the range of the query.
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.