Array range queries over range queries | CPP 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 add 1 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
#include <bits/stdc++.h> NEW_LINE #define max  10000 NEW_LINE using namespace std ; void update ( int arr [ ] , int l ) { arr [ l ] += arr [ l - 1 ] ; } 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 ++ ; } } void print ( int arr [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) cout << arr [ i ] << " ▁ " ; } int main ( ) { int n = 5 , m = 5 ; int arr [ n ] , record [ m ] ; int block_size = sqrt ( m ) ; int block [ max ] ; int command [ 5 ] [ 3 ] = { { 1 , 1 , 2 } , { 1 , 4 , 5 } , { 2 , 1 , 2 } , { 2 , 1 , 3 } , { 2 , 3 , 4 } } ; memset ( arr , 0 , sizeof arr ) ; memset ( record , 0 , sizeof record ) ; memset ( block , 0 , sizeof block ) ; 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 ) ; return 0 ; }