How to count the number of integers less then equals to X in the given range [ L , R ] in an array of size N ?
Solution : If we are able to count the number of integers less then equals to X in the range [ 1 , Y ]
then f( L , R , X ) = f( 1 , R , X ) - f( 1 , L - 1 , X ) where f ( 1 , Y , X ) is number of integer less then equals to X in the range [1 , Y]
Now, how to solve the above defined function efficiently in log(N) complexity.
Suppose if we are able to create N segment tree for each index where ith segment tree holds the information from index 1 to ith index , then query on the ith segment tree gives us the result for our function.
Now the problem arises , to create N segment tree with less space.
We should create only log(N) nodes for each segment tree , which store the information from index 1 to ith index , then during creating the ith segment tree we will retrieve the information of current node with the help of (i-1)th segment tree , hence our ith segment tree store the information from starting index to ith index. Total space complexity ( N * logN) , because for each index we are allocating only log(n) number of nodes.
We can construct Persistent segment tree with the help of pointers because we are building our segment tree at each index , and during construction to retrieve information from previous segment tree we just create link between nodes of current segment tree to the previous segment tree.
struct persistent{
persistent *left , *right;
int ct;
persistent(): left( NULL ) , right( NULL ) , ct( 0 ) { }
};
persistent *segment[100001];
persistent *update( persistent * *a , persistent *b , int l , int r , int idx ){
if( l greater then r )
return NULL;
if( (idx greater then equal l) and (idx less then equal r) ) {
b = new persistent(); // allocating the new node
int value = 1 ; // count = 1
if( *a != NULL)
value += (*a).ct; // retrieve the information from the previous tree
b.ct=value;
if( l != r){ // if it's not a leaf node
persistent *aa , *bb;
aa = NULL;
bb = NULL;
if(*a != NULL ){ // if a != NULL , means previous segment tree have
this node available then we can go to its left and
right node together with current segment tree node
aa = (*a).left;
bb = (*a).right;
}
b.left = update( &aa , b.left , l , (l + r)/2 , idx );
b.right= update( &bb , b.right, (l + r)/2 + 1 , r , idx);
}
return b;
}
else
return *a; // if index is out of range then we link it to the previous segment tree node
}
// it gives the number of integers in the range [s , e] for ith segment tree
int query( persistent * a , int l , int r , int s , int e ){
if( l > r || s > r || l > e || s > e )
return 0;
if(a == NULL )
return 0;
if(l >= s && r <= e )
return a -> ct;
return query( a -> left , l , (l + r)/2 , s , e) + query( a -> right , (l + r)/2 + 1 , r , s , e );
}
segment[0] = new persistent();
for(int i = 1 ; i <= N ; ++i )
segment[i] = update( &(segment[i-1]) , segment[i] , 1 , Maximum_value , Array );
Maximum value = maximum(Array ) , it will work for Maximum_value less then equal to 1e18
Example if array is : 3 , 1 , 5
segment[0] = node 1 : range[1,5] : ct = 0;
node 1 left = Null and node 1 right = Null
segment[1] = node 1 : range[1,5] : ct = 1;
node 1 right = segment[0] : node 1 right // because index is 3 and its range is [4,5] : out of range
node 1 left : range[1,3] : ct = 1; + (segment[0] : node 1 left : ct ( if available )
And so on…
Means every time if the current index is in the node range , then we should create the node and and update it with the previous tree node and move together the current pointer of current segment tree as well as previous , if the index is out of range , then we will create link of current node of current segment tree to the previous segment tree node