Queries to calculate sum of array elements present at every Yth index starting from the index X | Java program for the above approach ; Function to sum of arr [ x ] + arr [ x + y ] + arr [ x + 2 * y ] + ... for all possible values of X and Y , where Y is less than or equal to Math . sqrt ( N ) . ; Iterate over all possible values of X ; Precompute for all possible values of an expression such that y <= Math . sqrt ( N ) ; If i + j less than N ; Update dp [ i ] [ j ] ; Update dp [ i ] [ j ] ; Function to Find the sum of arr [ x ] + arr [ x + y ] + arr [ x + 2 * y ] + ... for all queries ; dp [ x ] [ y ] : Stores sum of arr [ x ] + arr [ x + y ] + arr [ x + 2 * y ] + ... ; Traverse the query array , Q [ ] [ ] ; If y is less than or equal to Math . sqrt ( N ) ; Stores the sum of arr [ x ] + arr [ x + y ] + arr [ x + 2 * y ] + ... ; Traverse the array , arr [ ] ; Update sum ; Update x ; Driver Code
import java . util . * ; class GFG { static int sz = 20 ; static int sqr = ( int ) ( Math . sqrt ( sz ) ) + 1 ; static void precomputeExpressionForAllVal ( int arr [ ] , int N , int dp [ ] [ ] ) { for ( int i = N - 1 ; i >= 0 ; i -- ) { for ( int j = 1 ; j <= Math . sqrt ( N ) ; j ++ ) { if ( i + j < N ) { dp [ i ] [ j ] = arr [ i ] + dp [ i + j ] [ j ] ; } else { dp [ i ] [ j ] = arr [ i ] ; } } } } static void querySum ( int arr [ ] , int N , int Q [ ] [ ] , int M ) { int [ ] [ ] dp = new int [ sz ] [ sqr ] ; precomputeExpressionForAllVal ( arr , N , dp ) ; for ( int i = 0 ; i < M ; i ++ ) { int x = Q [ i ] [ 0 ] ; int y = Q [ i ] [ 1 ] ; if ( y <= Math . sqrt ( N ) ) { System . out . print ( dp [ x ] [ y ] + " ▁ " ) ; continue ; } int sum = 0 ; while ( x < N ) { sum += arr [ x ] ; x += y ; } System . out . print ( sum + " ▁ " ) ; } } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 7 , 5 , 4 } ; int Q [ ] [ ] = { { 2 , 1 } , { 3 , 2 } } ; int N = arr . length ; int M = Q . length ; querySum ( arr , N , Q , M ) ; } }