Posts

Showing posts from December, 2013

Segment Trees, Tutorial, C++ Code and Applications

Image
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("%d %d",N, root->right->low);return 0;}
Node createSegmentT…