Array range queries over range queries | Java program to perform range queries over range queries . ; For prefix sum array ; This function is used to apply square root decomposition in the record array ; traversing first block in range ; traversing completely overlapped blocks in range ; traversing last block in range ; Function to print the resultant array ; Driver code ; If query is of type 2 then function call to record_func ; If query is of type 1 then simply add1 to the record array ; Merging the value of the block in the record array ; If query is of type 1 then the array elements are over - written by the record array ; The prefix sum of the array ; Printing the resultant array
public class GFG { static final int max = 10000 ; static void update ( int arr [ ] , int l ) { arr [ l ] += arr [ l - 1 ] ; } static void record_func ( int block_size , int block [ ] , int record [ ] , int l , int r , int value ) { while ( l < r && l % block_size != 0 && l != 0 ) { record [ l ] += value ; l ++ ; } while ( l + block_size <= r + 1 ) { block [ l / block_size ] += value ; l += block_size ; } while ( l <= r ) { record [ l ] += value ; l ++ ; } } static void print ( int arr [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) { System . out . print ( arr [ i ] + " ▁ " ) ; } } public static void main ( String [ ] args ) { int n = 5 , m = 5 ; int arr [ ] = new int [ n ] , record [ ] = new int [ m ] ; int block_size = ( int ) Math . sqrt ( m ) ; int block [ ] = new int [ max ] ; int command [ ] [ ] = { { 1 , 1 , 2 } , { 1 , 4 , 5 } , { 2 , 1 , 2 } , { 2 , 1 , 3 } , { 2 , 3 , 4 } } ; for ( int i = m - 1 ; i >= 0 ; i -- ) { if ( command [ i ] [ 0 ] == 2 ) { int x = i / ( block_size ) ; record_func ( block_size , block , record , command [ i ] [ 1 ] - 1 , command [ i ] [ 2 ] - 1 , ( block [ x ] + record [ i ] + 1 ) ) ; } else { record [ i ] ++ ; } } for ( int i = 0 ; i < m ; i ++ ) { int check = ( i / block_size ) ; record [ i ] += block [ check ] ; } for ( int i = 0 ; i < m ; i ++ ) { if ( command [ i ] [ 0 ] == 1 ) { arr [ command [ i ] [ 1 ] - 1 ] += record [ i ] ; if ( ( command [ i ] [ 2 ] - 1 ) < n - 1 ) { arr [ ( command [ i ] [ 2 ] ) ] -= record [ i ] ; } } } for ( int i = 1 ; i < n ; i ++ ) { update ( arr , i ) ; } print ( arr , n ) ; } }