Construction of Persistent Segment tree

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

3 Likes