text: Queries to calculate sum of array elements present at every Yth index starting from the index X | C ++ 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 sqrt ( N ) . ; Iterate over all possible values of X ; Precompute for all possible values of an expression such that y <= 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 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; const int sz = 20 ; const int sqr = int ( sqrt ( sz ) ) + 1 ; void precomputeExpressionForAllVal ( int arr [ ] , int N , int dp [ sz ] [ sqr ] ) { for ( int i = N - 1 ; i >= 0 ; i -- ) { for ( int j = 1 ; j <= sqrt ( N ) ; j ++ ) { if ( i + j < N ) { dp [ i ] [ j ] = arr [ i ] + dp [ i + j ] [ j ] ; } else { dp [ i ] [ j ] = arr [ i ] ; } } } } int querySum ( int arr [ ] , int N , int Q [ ] [ 2 ] , int M ) { int dp [ 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 <= sqrt ( N ) ) { cout << dp [ x ] [ y ] << " ▁ " ; continue ; } int sum = 0 ; while ( x < N ) { sum += arr [ x ] ; x += y ; } cout << sum << " ▁ " ; } } int main ( ) { int arr [ ] = { 1 , 2 , 7 , 5 , 4 } ; int Q [ ] [ 2 ] = { { 2 , 1 } , { 3 , 2 } } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int M = sizeof ( Q ) / sizeof ( Q [ 0 ] ) ; querySum ( arr , N , Q , M ) ; return 0 ; }