Range sum queries based on given conditions

0 0 13 minutes read

Given an array arr[] of N integers and matrix Queries[][] consisting of Q queries of the form {m, a, b}. For each query the task is to find the sum of array elements according to the following conditions:

If m = 1: Find the sum of the array elements in the range [a, b].
If m = 2: Rearrange the array elements in increasing order and find the sum of the elements in the range [a, b] in the new array.

Examples:

Input: arr[] = {6, 4, 2, 7, 2, 7}, Q = 3, Queries[][3] = {{2, 3, 6}, {1, 3, 4}, {1, 1, 6}}
Output: 24 9 28
Explanation:
For Query 1:
m is 2, then array after sorting is arr[] = {2, 2, 4, 6, 7, 7} and sum of element in the range [3, 6] is 4 + 6 + 7 + 7 = 24.
For Query 2:
m is 1, then original array is arr[] = {6, 4, 2, 7, 2, 7} and sum of element in the range [3, 4] is 2 + 7 = 9.
For Query 3:
m is 1, then original array is arr[] = {6, 4, 2, 7, 2, 7} and sum of element in the range [1, 6] is 6 + 4 + 2 + 7 + 2 + 7 = 28.

Input: arr[] = {5, 5, 2, 3}, Q = 3, Queries[][10] = {{1, 2, 4}, {2, 1, 4}, {1, 1, 1}, {2, 1, 4}, {2, 1, 2}, {1, 1, 1}, {1, 3, 3}, {1, 1, 3}, {1, 4, 4}, {1, 2, 2}}
Output: 10 15 5 15 5 5 2 12 3 5

Naive Approach: The idea is to traverse the given queries and find the sum of all the elements according to the given conditions:

Choose the array according to the given m, if m is equal to 1 then choose the original array otherwise choose the other array where all the elements of the array arr[] are sorted.
Now calculate the sum of the array between the range [a, b].
Iterate a loop over the range to find the sum.
Print the sum for each query.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the sum
// between the given range as per
// value of m
int range_sum(vector<int> v, int a,
              int b)
{
    // Stores the sum
    int sum = 0;
 
    // Loop to calculate the sum
    for (int i = a - 1; i < b; i++) {
        sum += v[i];
    }
 
    // Return sum
    return sum;
}
 
// Function to find the sum of elements
// for each query
void findSum(vector<int>& v1, int q,
             int Queries[][3])
{
    // Take a dummy vector
    vector<int> v2;
 
    // Size of vector
    int n = sizeof(v1) / sizeof(int);
 
    // Copying the elements into
    // dummy vector
    for (int i = 0; i < n; i++) {
        v2.push_back(v1[i]);
    }
 
    // Sort the dummy vector
    sort(v2.begin(), v2.end());
 
    // Performs operations
    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) {
 
            // Function Call to find sum
            cout << range_sum(v1, a, b)
                 << ' ';
        }
        else if (m == 2) {
 
            // Function Call to find sum
            cout << range_sum(v2, a, b)
                 << ' ';
        }
    }
}
 
// Driver Code
int main()
{
    // Given arr[]
    vector<int> arr = { 6, 4, 2, 7, 2, 7 };
 
    int Q = 1;
 
    // Given Queries
    int Queries[][3] = { { 2, 3, 6 } };
 
    // Function Call
    findSum(arr, Q, Queries);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to calculate the sum
// between the given range as per
// value of m
static int range_sum(Vector<Integer> v, int a,
                                        int b)
{
     
    // Stores the sum
    int sum = 0;
 
    // Loop to calculate the sum
    for(int i = a - 1; i < b; i++) 
    {
        sum += v.get(i);
    }
 
    // Return sum
    return sum;
}
 
static int range_sum(int []v, int a,
                     int b)
{
     
    // Stores the sum
    int sum = 0;
     
    // Loop to calculate the sum
    for(int i = a - 1; i < b; i++)
    {
        sum += v[i];
    }
     
    // Return sum
    return sum;
}
 
// Function to find the sum of elements
// for each query
static void findSum(int []v1, int q,
                    int Queries[][])
{
     
    // Take a dummy vector
    Vector<Integer> v2 = new Vector<Integer>();
 
    // Size of vector
    int n = v1.length;
 
    // Copying the elements into
    // dummy vector
    for(int i = 0; i < n; i++) 
    {
        v2.add(v1[i]);
    }
 
    // Sort the dummy vector
    Collections.sort(v2);
 
    // Performs operations
    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) 
        {
             
            // Function call to find sum
            System.out.print(range_sum(
                v1, a, b) + " ");
        }
        else if (m == 2) 
        {
 
            // Function call to find sum
            System.out.print(range_sum(
                v2, a, b) + " ");
        }
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given arr[]
    int []arr = { 6, 4, 2, 7, 2, 7 };
 
    int Q = 1;
 
    // Given Queries
    int Queries[][] = { { 2, 3, 6 } };
 
    // Function call
    findSum(arr, Q, Queries);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for the above approach
 
# Function to calculate the sum
# between the given range as per
# value of m
def range_sum(v, a, b):
 
    # Stores the sum
    Sum = 0
  
    # Loop to calculate the sum
    for i in range(a - 1, b):
        Sum += v[i]
  
    # Return sum
    return Sum
  
# Function to find the sum of elements
# for each query
def findSum(v1, q, Queries):
 
    # Take a dummy vector
    v2 = []
  
    # Size of vector
    n = len(v1)
  
    # Copying the elements into
    # dummy vector
    for i in range(n):
        v2.append(v1[i])
  
    # Sort the dummy vector
    v2.sort()
  
    # Performs operations
    for i in range(q):
        m = Queries[i][0]
        a = Queries[i][1]
        b = Queries[i][2]
  
        if (m == 1):
  
            # Function call to find sum
            print(range_sum(v1, a, b), end = " ")
             
        elif (m == 2):
  
            # Function call to find sum
            print(range_sum(v2, a, b), end = " ")
 
# Driver code
 
# Given arr[]
arr = [ 6, 4, 2, 7, 2, 7 ]
  
Q = 1
  
# Given Queries
Queries = [ [ 2, 3, 6 ] ]
  
# Function call
findSum(arr, Q, Queries)
 
# This code is contributed divyeshrabadiya07

C#

// C# program for the above approach
using System; 
using System.Collections; 
using System.Collections.Generic; 
using System.Text; 
 
class GFG{
     
// Function to calculate the sum
// between the given range as per
// value of m
static int range_sum(ArrayList v, int a,
                                  int b)
{
     
    // Stores the sum
    int sum = 0;
 
    // Loop to calculate the sum
    for(int i = a - 1; i < b; i++)
    {
        sum += (int)v[i];
    }
 
    // Return sum
    return sum;
}
 
// Function to find the sum of elements
// for each query
static void findSum(ArrayList v1, int q,
                    int [,]Queries)
{
     
    // Take a dummy vector
    ArrayList v2 = new ArrayList();
 
    // Size of vector
    int n = v1.Count;
 
    // Copying the elements into
    // dummy vector
    for(int i = 0; i < n; i++)
    {
        v2.Add(v1[i]);
    }
 
    // Sort the dummy vector
    v2.Sort();
 
    // Performs operations
    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) 
        {
             
            // Function call to find sum
            Console.Write(range_sum(v1, a, b));
            Console.Write(' ');
        }
        else if (m == 2)
        {
             
            // Function call to find sum
            Console.Write(range_sum(v2, a, b));
            Console.Write(' ');
        }
    }
}
 
// Driver Code
public static void Main(string[] args)
{
     
    // Given arr[]
    ArrayList arr=new ArrayList(){ 6, 4, 2,
                                   7, 2, 7 };
 
    int Q = 1;
 
    // Given Queries
    int [,]Queries = { { 2, 3, 6 } };
 
    // Function call
    findSum(arr, Q, Queries);
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to calculate the sum
// between the given range as per
// value of m
function range_sum(v, a, b)
{
     
    // Stores the sum
    let sum = 0;
      
    // Loop to calculate the sum
    for(let i = a - 1; i < b; i++)
    {
        sum += v[i];
    }
      
    // Return sum
    return sum;
}
 
// Function to find the sum of elements
// for each query
function findSum(v1, q, Queries)
{
     
    // Take a dummy vector
    let v2 = [];
  
    // Size of vector
    let n = v1.length;
  
    // Copying the elements into
    // dummy vector
    for(let i = 0; i < n; i++)
    {
        v2.push(v1[i]);
    }
  
    // Sort the dummy vector
    v2.sort(function(a, b){return a - b;});
  
    // Performs operations
    for(let i = 0; i < q; i++)
    {
        let m = Queries[i][0];
        let a = Queries[i][1];
        let b = Queries[i][2];
  
        if (m == 1)
        {
             
            // Function call to find sum
            document.write(range_sum(
                v1, a, b) + " ");
        }
        else if (m == 2)
        {
  
            // Function call to find sum
            document.write(range_sum(
                v2, a, b) + " ");
        }
    }
}
 
// Driver Code
 
// Given arr[]
let arr = [ 6, 4, 2, 7, 2, 7 ];
let Q = 1;
 
// Given Queries
let Queries = [ [ 2, 3, 6 ] ];
 
// Function call
findSum(arr, Q, Queries);
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Output:

Time Complexity: O(N²)
Auxiliary Space: O(N)

Efficient Approach: The above approach can be optimized by reducing one loop using the prefix sum array. Below are the steps:

Create the other array brr[] to store the elements of the given array arr[] in sorted order.
Find the prefix sum of both the arrays arr[] and brr[].
Traverse the given queries and if the query is of type 1 then the sum of the element in the range [a, b] is given by:

arr[b – 1] – arr[a – 2]

If the query is of type 2 then the sum of the element in the range [a, b] is given by:

brr[b – 1] – arr[a – 2]

Below is the implementation of the above approach:

C++

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

Java

// Java program for the above approach
import java.util.*;
  
class GFG{
     
// Function to calculate the sum
// between the given range as per
// value of m
static int range_sum(int []arr, int a,
                     int b)
{
     
    // Stores the sum
    int sum = 0;
  
    // Condition for a to print the
    // sum between ranges [a, b]
    if (a - 2 < 0)
        sum = arr[b - 1];
    else
        sum = arr[b - 1] - arr[a - 2];
  
    // Return sum
    return sum;
}
  
// Function to precalculate the sum
// of both the vectors
static void precompute_sum(int []arr, 
                           int []brr)
{
    int N = (int)arr.length;
  
    // Make Prefix sum array
    for(int i = 1; i < N; i++)
    {
        arr[i] = arr[i] + arr[i - 1];
        brr[i] = brr[i] + brr[i - 1];
    }
}
  
// Function to compute the result
// for each query
static void find_sum(int []arr, int q,
                     int Queries[][])
{
     
    // Take a dummy vector and copy
    // the element of arr in brr
    int []brr = arr.clone();
  
    int N = (int)arr.length;
  
    // Sort the dummy vector
    Arrays.sort(brr);
  
    // Compute prefix sum of both vectors
    precompute_sum(arr, brr);
  
    // Performs operations
    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)
        {
             
            // Function call to find sum
            System.out.print(range_sum(
                arr, a, b) + " ");
        }
        else if (m == 2) 
        {
             
            // Function call to find sum
            System.out.print(range_sum(
                brr, a, b) + " ");
        }
    }
}
  
// Driver Code
public static void main(String[] args)
{
     
    // Given arr[]
    int []arr = { 0, 6, 4, 2, 7, 2, 7 };
     
    // Number of queries
    int Q = 1;
  
    // Given queries
    int Queries[][] = { { 2, 3, 6 } };
  
    // Function call
    find_sum(arr, Q, Queries);
}
}
  
// This code is contributed by Amit Katiyar

Python3

# Python3 program for 
# the above approach
 
# Function to calculate 
# the sum between the 
# given range as per value 
# of m
def range_sum(arr, a, b):
 
    # Stores the sum
    sum = 0
 
    # Condition for a to 
    # print the sum between 
    # ranges [a, b]
    if (a - 2 < 0):
        sum = arr[b - 1]
    else:
        sum = (arr[b - 1] -
               arr[a - 2])
 
    # Return sum
    return sum
 
# Function to precalculate 
# the sum of both the vectors
def precompute_sum(arr, brr):
 
    N = len(arr)
 
    # Make Prefix sum array
    for i in range(1, N):
        arr[i] = arr[i] + arr[i - 1]
        brr[i] = brr[i] + brr[i - 1]
 
# Function to compute 
# the result for each query
def find_sum(arr, q, Queries):
 
    # Take a dummy vector 
    # and copy the element 
    # of arr in brr
    brr = arr.copy()
 
    N = len(arr)
 
    # Sort the dummy vector
    brr.sort()
 
    # Compute prefix sum of 
    # both vectors
    precompute_sum(arr, brr)
 
    # Performs operations
    for i in range(q):
 
        m = Queries[i][0]
        a = Queries[i][1]
        b = Queries[i][2]
 
        if (m == 1):
 
            # Function Call to 
            # find sum
            print (range_sum(arr, 
                             a, b), 
                   end = ' ')
         
        elif (m == 2):
 
            # Function Call to 
            # find sum
            print (range_sum(brr, 
                             a, b), 
                   end = ' ')
 
# Driver Code
if __name__ == "__main__":
   
    # Given arr[]
    arr = [0, 6, 4, 
           2, 7, 2, 7]
 
    # Number of queries
    Q = 1
 
    # Given queries
    Queries = [[2, 3, 6]]
 
    # Function Call
    find_sum(arr, Q, Queries)
 
# This code is contributed by Chitranayal

C#

// C# program for 
// the above approach
using System;
class GFG{
     
// Function to calculate the sum
// between the given range as per
// value of m
static int range_sum(int []arr, 
                     int a,
                     int b)
{
  // Stores the sum
  int sum = 0;
 
  // Condition for a to print the
  // sum between ranges [a, b]
  if (a - 2 < 0)
    sum = arr[b - 1];
  else
    sum = arr[b - 1] - arr[a - 2];
 
  // Return sum
  return sum;
}
  
// Function to precalculate the sum
// of both the vectors
static void precompute_sum(int []arr, 
                           int []brr)
{
  int N = (int)arr.Length;
 
  // Make Prefix sum array
  for(int i = 1; i < N; i++)
  {
    arr[i] = arr[i] + arr[i - 1];
    brr[i] = brr[i] + brr[i - 1];
  }
}
  
// Function to compute the result
// for each query
static void find_sum(int []arr, int q,
                     int [,]Queries)
{    
  // Take a dummy vector and copy
  // the element of arr in brr
  int []brr = new int[arr.Length];
  arr.CopyTo(brr, 0);
 
  int N = (int)arr.Length;
 
  // Sort the dummy vector
  Array.Sort(brr);
 
  // Compute prefix sum of both vectors
  precompute_sum(arr, brr);
 
  // Performs operations
  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)
    {
      // Function call to find sum
      Console.Write(range_sum(
                    arr, a, b) + " ");
    }
    else if (m == 2) 
    {
      // Function call to find sum
      Console.Write(range_sum(
                    brr, a, b) + " ");
    }
  }
}
  
// Driver Code
public static void Main(String[] args)
{
  // Given []arr
  int []arr = {0, 6, 4, 2, 7, 2, 7};
 
  // Number of queries
  int Q = 1;
 
  // Given queries
  int [,]Queries = {{2, 3, 6}};
 
  // Function call
  find_sum(arr, Q, Queries);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript program for the above approach
 
// Function to calculate the sum
// between the given range as per
// value of m
function range_sum(arr,a,b)
{
    // Stores the sum
    let sum = 0;
   
    // Condition for a to print the
    // sum between ranges [a, b]
    if (a - 2 < 0)
        sum = arr[b - 1];
    else
        sum = arr[b - 1] - arr[a - 2];
   
    // Return sum
    return sum;
}
 
// Function to precalculate the sum
// of both the vectors
function precompute_sum(arr,brr)
{
    let N = arr.length;
   
    // Make Prefix sum array
    for(let i = 1; i < N; i++)
    {
        arr[i] = arr[i] + arr[i - 1];
        brr[i] = brr[i] + brr[i - 1];
    }
}
 
// Function to compute the result
// for each query
function find_sum(arr,q,Queries)
{
    // Take a dummy vector and copy
    // the element of arr in brr
    let brr = [...arr];
   
    let N = arr.length;
   
    // Sort the dummy vector
    brr.sort(function(a,b){return a-b;});
   
    // Compute prefix sum of both vectors
    precompute_sum(arr, brr);
   
    // Performs operations
    for(let i = 0; i < q; i++)
    {
        let m = Queries[i][0];
        let a = Queries[i][1];
        let b = Queries[i][2];
   
        if (m == 1)
        {
              
            // Function call to find sum
            document.write(range_sum(
                arr, a, b) + " ");
        }
        else if (m == 2)
        {
              
            // Function call to find sum
            document.write(range_sum(
                brr, a, b) + " ");
        }
    }
}
 
// Driver Code
let arr=[0, 6, 4, 2, 7, 2, 7];
// Number of queries
let Q = 1;
 
// Given queries
let Queries = [[ 2, 3, 6 ]];
 
// Function call
find_sum(arr, Q, Queries);
 
 
// This code is contributed by rag2127
</script>

Output:

Time Complexity: O(N*log N)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!