### 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]**

**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:

- #include <iostream>
- #include <stdio.h>
- #include <stdlib.h>
- using namespace std;
- typedef struct segmentTreeNode* Node;
- struct segmentTreeNode {
- int low;
- int high;
- Node left;
- Node right;
- } segmentTreeNode;
- Node createSegmentTree(int low, int high);
- int main() {
- int N = 9;
- Node root=createSegmentTree(0,N-1);
- printf("%d %d",N, root->right->low);
- return 0;
- }
- Node createSegmentTree(int low, int high) {
- Node root=(Node)malloc(sizeof(segmentTreeNode));
- root->low = low;
- root->high = high;
- root->left = 0;
- root->right = 0;
- if(low != high) {
- Node left = createSegmentTree(low, (low+high)/2);
- Node right = createSegmentTree(((low+high)/2)+1,high);
- root->left=left;
- root->right=right;
- }
- return root;
- }

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

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

## Comments

## Post a Comment