Sqrt ( or Square Root ) Decomposition Technique | Set 1 ( Introduction ) | Python 3 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 ; 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 .
from math import sqrt NEW_LINE MAXN = 10000 NEW_LINE SQRSIZE = 100 NEW_LINE arr = [ 0 ] * ( MAXN ) NEW_LINE block = [ 0 ] * ( SQRSIZE ) NEW_LINE blk_sz = 0 NEW_LINE def update ( idx , val ) : NEW_LINE INDENT blockNumber = idx // blk_sz NEW_LINE block [ blockNumber ] += val - arr [ idx ] NEW_LINE arr [ idx ] = val NEW_LINE DEDENT def query ( l , r ) : NEW_LINE INDENT sum = 0 NEW_LINE while ( l < r and l % blk_sz != 0 and l != 0 ) : NEW_LINE INDENT sum += arr [ l ] NEW_LINE l += 1 NEW_LINE DEDENT while ( l + blk_sz <= r ) : NEW_LINE INDENT sum += block [ l // blk_sz ] NEW_LINE l += blk_sz NEW_LINE DEDENT while ( l <= r ) : NEW_LINE INDENT sum += arr [ l ] NEW_LINE l += 1 NEW_LINE DEDENT return sum NEW_LINE DEDENT def preprocess ( input , n ) : NEW_LINE INDENT blk_idx = - 1 NEW_LINE global blk_sz NEW_LINE blk_sz = int ( sqrt ( n ) ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT arr [ i ] = input [ i ] ; NEW_LINE if ( i % blk_sz == 0 ) : NEW_LINE INDENT blk_idx += 1 ; NEW_LINE DEDENT block [ blk_idx ] += arr [ i ] NEW_LINE DEDENT DEDENT input = [ 1 , 5 , 2 , 4 , 6 , 1 , 3 , 5 , 7 , 10 ] NEW_LINE n = len ( input ) NEW_LINE preprocess ( input , n ) NEW_LINE print ( " query ( 3,8 ) ▁ : ▁ " , query ( 3 , 8 ) ) NEW_LINE print ( " query ( 1,6 ) ▁ : ▁ " , query ( 1 , 6 ) ) NEW_LINE update ( 8 , 0 ) NEW_LINE print ( " query ( 8,8 ) ▁ : ▁ " , query ( 8 , 8 ) ) NEW_LINE