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. Node createSegmentTree(int low, int high) {
  20. Node root=(Node)malloc(sizeof(segmentTreeNode));
  21. root->low = low;
  22. root->high = high;
  23. root->left = 0;
  24. root->right = 0;
  25. if(low != high) {
  26. Node left = createSegmentTree(low, (low+high)/2);
  27. Node right = createSegmentTree(((low+high)/2)+1,high);
  28. root->left=left;
  29. root->right=right;
  30. }
  31. return root;
  32. }

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

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

Comments

Popular posts from this blog

C Graph implementation with adjacency list representation using structures: Data Structure Tutorial 1

Accessing DynamoDB from Spring Java application - Walkthrough tutorial

Interview Of An Indian Top Coder : Rudradev Basak