Range sum queries based on given conditions | C ++ program for the above approach ; Function to calculate the sum between the given range as per value of m ; Stores the sum ; Condition for a to print the sum between ranges [ a , b ] ; Return sum ; Function to precalculate the sum of both the vectors ; Make Prefix sum array ; Function to compute the result for each query ; Take a dummy vector and copy the element of arr in brr ; Sort the dummy vector ; Compute prefix sum of both vectors ; Performs operations ; Function Call to find sum ; Function Call to find sum ; Driver Code ; Given arr [ ] ; Number of queries ; Given queries ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int range_sum ( vector < int > & arr , int a , int b ) { int sum = 0 ; if ( a - 2 < 0 ) sum = arr [ b - 1 ] ; else sum = arr [ b - 1 ] - arr [ a - 2 ] ; return sum ; } void precompute_sum ( vector < int > & arr , vector < int > & brr ) { int N = ( int ) arr . size ( ) ; for ( int i = 1 ; i <= N ; i ++ ) { arr [ i ] = arr [ i ] + arr [ i - 1 ] ; brr [ i ] = brr [ i ] + brr [ i - 1 ] ; } } void find_sum ( vector < int > & arr , int q , int Queries [ ] [ 3 ] ) { vector < int > brr ( arr ) ; int N = ( int ) arr . size ( ) ; sort ( brr . begin ( ) , brr . end ( ) ) ; precompute_sum ( arr , brr ) ; for ( int i = 0 ; i < q ; i ++ ) { int m = Queries [ i ] [ 0 ] ; int a = Queries [ i ] [ 1 ] ; int b = Queries [ i ] [ 2 ] ; if ( m == 1 ) { cout << range_sum ( arr , a , b ) << ' ▁ ' ; } else if ( m == 2 ) { cout << range_sum ( brr , a , b ) << ' ▁ ' ; } } } int main ( ) { vector < int > arr = { 0 , 6 , 4 , 2 , 7 , 2 , 7 } ; int Q = 1 ; int Queries [ ] [ 3 ] = { { 2 , 3 , 6 } } ; find_sum ( arr , Q , Queries ) ; return 0 ; }