[Algorithms] Segment Trees

Sources: TopCoder, LetUsKode, StackOverFlow and Google. 
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
http://zobayer.blogspot.in/ 

Segment Trees mostly used for storing data and to provide easy access in range queries.

Basic Idea:

Each non-Leaf Node summarizes the information stored at descenedent leaves.
In Other words, Node 'i' will have summarized info about child Nodes at Kth Level.
    i.e. childs from i*2^k to (i+1)*s^k -1

Majorly two Operations are can be performed on a node in segTrees.
    Merge:     Summarize info stored at descendant nodes.
    Split:    Applying certain operations on descendant nodes.

And the following operations are done one the whole segTree.
    Initialize:    Initialize the segment tree.
    Update:     Update info of the leaf node and propagate the change till the root.
    Query:    Query function to be run over a Range or on a specific node(To check balanced state).

Generalized Code Template (In C++): [Node Structure and Operations done on a Node]

//
//Node Structure
struct node{
        <type> <variable> ;

        node merge(node& l, node& r){
            //Apply your merge logic here.
        }

        node split(node& l, node& r){
            //Apply Split logic here if you have any
        }

        node setValue(){
            //Initialize variable in case of Leafnode creation or updation of a LeafNode
        }

};

Generalized Code Template (In C++): [Operation that can be performed on segTree]

//
// initialization of Nodes
    void init(int Node, int i, int j) {
        if(i==j) { // Initialize Leaf Nodes
            T[Node].setValue();
            return;
        }else{ // Summerize Descendant Nodes Nodes
            int m = (i+j)/2;
            init(2*Node, i, m);
            init(2*Node+1, m+1, j);
            T[Node].merge(T[2*Node],T[2*Node+1]);
        }
    }

//
// Update element with index 'idx' in the range [i,j]
void update(int Node, int i, int j,int idx, <values>) {
        if(i==j && i == idx) { // Update the LeafNode idx
            T[Node].setValue();
            return;
        }else{ // Summerize Descendant Nodes Nodes
            int m = (i+j)/2;
            if(idx <=m)
                update(2*Node, i, m, idx, <values>);
            else
                update(2*Node+1, m+1, j, idx, <values>);
            T[Node].merge(T[2*Node],T[2*Node+1]);
        }
    }

//
// Search for Node having interval info [L,R] in [i,j]; (i <= L < R <= r)
 void range_query(node& resultNode,int Node,int i, int j, int L, int R){
        if(i==L && j==R){
            resultNode = T[Node];
            return;
        }else{
            int m = (i+j)/2;
            if( R <= m )
                range_query(resultNode, 2*Node,  i, m, L, R);
            else if( L > m )
                range_query(resultNode, 2*Node+1, m+1, j, L, R);
            else{
                node left,right;
                range_query(left, 2*Node,  i, m, L, m);
                range_query(right, 2*Node+1, m+1, j, m+1, R);
                resultNode.merge(left,right);
            }
        }
    }

Practice Problems:
http://www.spoj.pl/problems/BRCKTS/  
http://www.spoj.com/problems/GSS3/
http://www.spoj.pl/problems/GSS1/