Queries to calculate the Sum of Array elements in the range [ L , R ] having indices as multiple of K | C ++ Program to implement the above approach ; Structure of a Query ; Function to calculate the sum of array elements at indices from range [ L , R ] which are multiples of K for each query ; Stores Prefix Sum ; prefixSum [ i ] [ j ] : Stores the sum from indices [ 0 , j ] which are multiples of i ; If index j is a multiple of i ; Compute prefix sum ; Otherwise ; Traverse each query ; Sum of all indices upto R which are a multiple of K ; Sum of all indices upto L - 1 which are a multiple of K ; Calculate the difference ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int L ; int R ; int K ; } ; int kMultipleSum ( int arr [ ] , Node Query [ ] , int N , int Q ) { int prefixSum [ N + 1 ] [ N ] ; for ( int i = 1 ; i <= N ; i ++ ) { prefixSum [ i ] [ 0 ] = arr [ 0 ] ; for ( int j = 0 ; j < N ; j ++ ) { if ( j % i == 0 ) { prefixSum [ i ] [ j ] = arr [ j ] + prefixSum [ i ] [ j - 1 ] ; } else { prefixSum [ i ] [ j ] = prefixSum [ i ] [ j - 1 ] ; } } } for ( int i = 0 ; i < Q ; i ++ ) { int last = prefixSum [ Query [ i ] . K ] [ Query [ i ] . R ] ; int first ; if ( Query [ i ] . L == 0 ) { first = prefixSum [ Query [ i ] . K ] [ Query [ i ] . L ] ; } else { first = prefixSum [ Query [ i ] . K ] [ Query [ i ] . L - 1 ] ; } cout << last - first << endl ; } } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 , 6 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int Q = 2 ; Node Query [ Q ] ; Query [ 0 ] . L = 2 , Query [ 0 ] . R = 5 , Query [ 0 ] . K = 2 ; Query [ 1 ] . L = 3 , Query [ 1 ] . R = 5 , Query [ 1 ] . K = 5 ; kMultipleSum ( arr , Query , N , Q ) ; }