CSES Solutions – Static Range Sum Queries
Given an array arr[] of N integers, your task is to process Q queries of the form: what is the sum of values in range [a,b]?
Examples
Input: arr[] = {1, 3, 4, 8, 6, 1, 4, 2}, Queries: {{2, 5}, {1, 3}}
Output: 21 8
Explanation:
- Query 1: Sum of elements from index 2 to 5 = 3 + 4 + 8 + 6 = 21
- Query 2: Sum of elements from index 1 to 3 = 1 + 3 + 4 = 8
Input: arr[] = {3, 2, 4, 5, 1, 1, 5, 3} Queries: {{2, 4}, {5, 6}, {1, 8}, {3, 3}}
Output: 11 2 24 4
Explanation:
- Query 1: Sum of elements from position 2 to 4 = 2 + 4 + 5 = 11
- Query 2: Sum of elements from position 5 to 6 = 1 + 1 = 2
- Query 3: Sum of elements from position 1 to 8 = 3 + 2 + 4 + 5 + 1 + 1 + 5 + 3 = 24
- Query 4: Sum of elements from position 3 to 3 = 4
Algorithm: To solve the problem, follow the below idea:
We can solve this problem using Prefix Sum approach.
- Pre-processing: Compute prefix sums for the array.
- Query Processing: Find the sum of the elements between the range l and r , i.e. prefixSum[r] – prefixSum[l-1].
Step-by-step algorithm:
- Create a prefix sum array prefixSum of the size n+1, where n is the size of input array.
- Initialize prefixSum[0] to 0 and compute prefixSum[i] = prefixSum[i-1] + array[i-1] for i from 1 to n.
- To answer a query [l, r] return prefixSum[r+1] – prefixSum[l].
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// function to solve all the static range queries
vector<ll> solve(vector<ll>& arr,
vector<vector<ll> >& queries, ll n, ll q)
{
// Creating a prefix Sum Array
vector<ll> prefixSum(n + 1, 0);
for (int i = 1; i <= n; ++i) {
prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
}
// Creating Result array to store the result of each
// query
vector<ll> result;
for (auto& query : queries) {
ll l = query[0], r = query[1];
ll sum = prefixSum[r] - prefixSum[l - 1];
result.push_back(sum);
}
return result;
}
int main()
{
// Sample Input
ll n = 8, q = 4;
vector<ll> arr = { 3, 2, 4, 5, 1, 1, 5, 3 };
vector<vector<ll> > queries
= { { 2, 4 }, { 5, 6 }, { 1, 8 }, { 3, 3 } };
// Function Call
vector<ll> result = solve(arr, queries, n, q);
for (ll sum : result) {
cout << sum << " ";
}
cout << endl;
return 0;
}
import java.util.*;
public class Main {
// Function to solve all the static range queries
public static List<Long> solve(List<Long> arr, List<List<Long>> queries, int n, int q) {
// Creating a prefix Sum Array
List<Long> prefixSum = new ArrayList<>(Collections.nCopies(n + 1, 0L));
for (int i = 1; i <= n; ++i) {
prefixSum.set(i, prefixSum.get(i - 1) + arr.get(i - 1));
}
// Creating Result array to store the result of each query
List<Long> result = new ArrayList<>();
for (List<Long> query : queries) {
long l = query.get(0), r = query.get(1);
long sum = prefixSum.get((int)r) - prefixSum.get((int)l - 1);
result.add(sum);
}
return result;
}
public static void main(String[] args) {
// Sample Input
int n = 8, q = 4;
List<Long> arr = Arrays.asList(3L, 2L, 4L, 5L, 1L, 1L, 5L, 3L);
List<List<Long>> queries = Arrays.asList(
Arrays.asList(2L, 4L),
Arrays.asList(5L, 6L),
Arrays.asList(1L, 8L),
Arrays.asList(3L, 3L)
);
// Function Call
List<Long> result = solve(arr, queries, n, q);
for (Long sum : result) {
System.out.print(sum + " ");
}
System.out.println();
}
}
# function to solve all the static range queries
def solve(arr, queries):
# Creating a prefix Sum Array
prefix_sum = [0] * (len(arr) + 1)
for i in range(1, len(arr) + 1):
prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]
# Creating Result array to store the result of each query
result = []
for query in queries:
l, r = query[0], query[1]
# Calculating sum for the current query range
sum_val = prefix_sum[r] - prefix_sum[l - 1]
result.append(sum_val)
return result
# Sample Input
arr = [3, 2, 4, 5, 1, 1, 5, 3]
queries = [[2, 4], [5, 6], [1, 8], [3, 3]]
# Function Call
result = solve(arr, queries)
for sum_val in result:
print(sum_val, end=" ")
print()
function GFG(arr, queries) {
// Creating a prefix Sum Array
let prefixSum = new Array(arr.length + 1).fill(0);
for (let i = 1; i <= arr.length; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
}
// Creating Result array to store the result of the each query
let result = [];
for (let query of queries) {
let l = query[0], r = query[1];
// Calculating sum for current query range
let sumVal = prefixSum[r] - prefixSum[l - 1];
result.push(sumVal);
}
return result;
}
// Sample Input
let arr = [3, 2, 4, 5, 1, 1, 5, 3];
let queries = [[2, 4], [5, 6], [1, 8], [3, 3]];
// Function Call
let result = GFG(arr, queries);
console.log(result.join(" "));
Output
11 2 24 4
Time Complexity : O(N + Q), where N is the number of elements in arr[] and Q is the number of queries.
Auxiliary Space: O(N)