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: #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(&quo