Segment Trees, Tutorial, C++ Code and Applications

A segment tree is a heap-like data structure that can be used for making update/query operations upon array intervals in logarithmical time. We define the segment tree for the interval [i, j] in the following recursive manner:

• the first node will hold the information for the interval [i, j]
• if i<j the left and right son will hold the information for the intervals [i, (i+j)/2] and [(i+j)/2+1, j]

Notice that the height of a segment tree for an interval with N elements is [logN] + 1. Here is how a segment tree for the interval [0, 9] would look like: 

Code for creating a segment tree recursively:

1. #include <iostream>
2. #include <stdio.h>
3. #include <stdlib.h>
4. using namespace std;
5. typedef struct segmentTreeNode* Node;
6. struct segmentTreeNode {
7. int low;
8. int high;
9. Node left;
10. Node right;
11. } segmentTreeNode;
12. Node createSegmentTree(int low, int high);
13. int main() {
14.         int N = 9;
15. Node root=createSegmentTree(0,N-1);
16. printf("%d %d",N, root->right->low);
17. return 0;
18. }
19. 
    
20. Node createSegmentTree(int low, int high) {
21. Node root=(Node)malloc(sizeof(segmentTreeNode));
22. root->low = low;
23. root->high = high;
24. root->left = 0;
25. root->right = 0;
26. if(low != high) {
27. Node left = createSegmentTree(low, (low+high)/2);
28. Node right = createSegmentTree(((low+high)/2)+1,high);
29. root->left=left;
30. root->right=right;
31. }
32. return root;
33. }

Applications: Range Minimum Query (RMQ) problems , Least Common Ancestor (LCA) problems etc.

For clarifications/suggesions, the comments section is all yours :)