Finding the Longest Increasing Subsequence using Segment Tre

/*
Explained: Finding the Longest Increasing Subsequence using Segment Tree
Tutorial - http://manzzup.blogspot.com/2015/08/explained-finding-longest-increasing.html
*/
#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

//define a type p just a pair
typedef pair<int,int> p;

//function to compare two pairs
int compare(p p1,p p2){
    if(p1.first == p2.first){
        //note that if the element values are equal the latter element of original array comes first
        return p1.second > p2.second;
    }
    return p1.first < p2.first;
}

//building the segment tree - more like updating the initial tree
void buildTree(int* tree,int pos,int low,int high,int ind,int val){
    //ind - is the original index of current element
    //if ind is out of range of the current range, just stop
    if(ind < low || ind > high) return;
    //if low == high then the current position should be updated to the value
    if(low == high){
        tree[pos] = val;
        return;
    }

    //take the mid point
    int mid = (high+low)/2;

    //recursivly call the function on the child nodes
    buildTree(tree,2*pos + 1,low,mid,ind,val);
    buildTree(tree,2*pos + 2,mid+1,high,ind,val);

    //assign the current position the max of the 2 child nodes
    tree[pos] = max(tree[2*pos + 1],tree[2*pos + 2]);
}

//function to query the tree and find the maximum in given range upto now
int findMax(int* tree,int pos,int low,int high,int st,int ed){
    //uses the 3 rules of segment tree query
    //if the current range is totally inside the query range return the value of current position
    if(low >= st && high <= ed){
        return tree[pos];
    }
    //if it's out of bounds, return the minimum which would be 0 in this case
    if(st > high || ed < low){
        return 0;
    }


    int mid = (high+low)/2;

    //else do the findMax on child nodes and return the maximum of the two
    return max(findMax(tree,2*pos + 1,low,mid,st,ed),findMax(tree,2*pos + 2,mid+1,high,st,ed));
}

int main(){
    int ary[] = {3,1,2,8;

    int n = 4;
    //generate the ary of pairs, we use pairs to store both the element and the index
    p* pairs = new p[n];
    for(int i=0;i<n;i++){
        pairs[i].first = ary[i];
        pairs[i].second = i;
    }

    //using custom sorter to sort the array
    sort(pairs,pairs+n,compare);

    //the max length of segment tree is 2x(nearest power of 2 near n) - 1
    int len = pow(2,(int)(ceil(sqrt(n))) + 1) - 1;
    int* tree = new int[len];

    //loop all the pairs and update the tree
    for(int i=0;i<n;i++){
        buildTree(tree,0,0,n-1,pairs[i].second,findMax(tree,0,0,n-1,0,pairs[i].second) + 1);
    }

    //print the end tree just for debug
    for(int i=0;i<len;i++){
        cout << tree[i] << " ";
    }
    cout << endl;

    //print the value of the longest subsequenc which is the root value
    cout << tree[0] << endl;



}