Sqrt ( or Square Root ) Decomposition Technique | Set 1 ( Introduction ) | C ++ program to demonstrate working of Square Root Decomposition . ; original array ; decomposed array ; block size ; Time Complexity : O ( 1 ) ; Time Complexity : O ( sqrt ( n ) ) ; traversing first block in range ; traversing completely overlapped blocks in range ; traversing last block in range ; Fills values in input [ ] ; initiating block pointer ; calculating size of block ; building the decomposed array ; entering next block incementing block pointer ; Driver code ; We have used separate array for input because the purpose of this code is to explain SQRT decomposition in competitive programming where we have multiple inputs .
#include " iostream " NEW_LINE #include " math . h " NEW_LINE using namespace std ; #define MAXN  10000 NEW_LINE #define SQRSIZE  100 NEW_LINE int arr [ MAXN ] ; int block [ SQRSIZE ] ; int blk_sz ; void update ( int idx , int val ) { int blockNumber = idx / blk_sz ; block [ blockNumber ] += val - arr [ idx ] ; arr [ idx ] = val ; } int query ( int l , int r ) { int sum = 0 ; while ( l < r and l % blk_sz != 0 and l != 0 ) { sum += arr [ l ] ; l ++ ; } while ( l + blk_sz <= r ) { sum += block [ l / blk_sz ] ; l += blk_sz ; } while ( l <= r ) { sum += arr [ l ] ; l ++ ; } return sum ; } void preprocess ( int input [ ] , int n ) { int blk_idx = -1 ; blk_sz = sqrt ( n ) ; for ( int i = 0 ; i < n ; i ++ ) { arr [ i ] = input [ i ] ; if ( i % blk_sz == 0 ) { blk_idx ++ ; } block [ blk_idx ] += arr [ i ] ; } } int main ( ) { int input [ ] = { 1 , 5 , 2 , 4 , 6 , 1 , 3 , 5 , 7 , 10 } ; int n = sizeof ( input ) / sizeof ( input [ 0 ] ) ; preprocess ( input , n ) ; cout << " query ( 3,8 ) ▁ : ▁ " << query ( 3 , 8 ) << endl ; cout << " query ( 1,6 ) ▁ : ▁ " << query ( 1 , 6 ) << endl ; update ( 8 , 0 ) ; cout << " query ( 8,8 ) ▁ : ▁ " << query ( 8 , 8 ) << endl ; return 0 ; }