Day 1 of 60 Days of DSA: Subarray Sums & Range Queries

Learn how to calculate subarray sums efficiently — from brute force to prefix sums.

Concept 1: Sum of All Subarray Sums

Problem:

You are given an integer array A of length N. You have to find the sum of all subarray sums of A. More formally, a subarray is defined as a contiguous part of an array which we can obtain by deleting zero or more elements from either end of the array. A subarray sum denotes the sum of all the elements of that subarray.

Example:

Input 1: A = [1, 2, 3]
Input 2: A = [2, 1, 3]

Example Output

Output 1: 20
Output 2: 19

Example Explanation

Explanation 1: The different subarrays for the given array are: [1], [2], [3], [1, 2], [2, 3], [1, 2, 3].
Their sums are: 1 + 2 + 3 + 3 + 5 + 6 = 20
Explanation 2: The different subarrays for the given array are: [2], [1], [3], [2, 1], [1, 3], [2, 1, 3].
Their sums are: 2 + 1 + 3 + 3 + 4 + 6 = 19

Brute Force

To find all subarrays and then calculate their sum — Time complexity — O(N*N)

Optimised: Contribution Technique

1. Find how many times each element is contributing to the subarrays
2. Adding contribution of each number
Ex Input— [1,2,3]
Subrrays — [1], [1,2], [1,2,3], [2], [2,3], [3]
1 is contributing 3 times = 1*3 =3
2 is contributing 4 times = 2*4 = 8
3 is contributing 3 times = 3*3 =9
Total = 3+8+9=20

Each element contributes to (i+1) * (n-i) subarrays.

// Main function
function sumofAllSubArrays(A){
 let sum =0;
 for(let i=0; i< A.length; i++){
 sum += findContributionOfIthNumber(A, i);
 }
 return sum;
}

function findContributionOfIthNumber(arr, i){
 let n = arr.length;
 let times = (i+1)* (n-i);
 return arr[i]*times;
}

console.log(sumofAllSubArrays([1, 2, 3]));
console.log(sumofAllSubArrays([2, 1, 3]));

Output:
sumofAllSubArrays([1,2,3]) → 20

⏱️ Time Complexity: O(N)
🧠 Space Complexity: O(1)

Concept 2: Range Sum Query

Problem:

You are given an integer array A of length N. You are also given a 2D integer array B with dimensions M x 2, where each row denotes a [L, R] query. For each query, you have to find the sum of all elements from L to R indices in A (0 — indexed). More formally, find A[L] + A[L + 1] + A[L + 2] +… + A[R — 1] + A[R] for each query.

Example Input

Input 1: A = [1, 2, 3, 4, 5], B = [[0, 3], [1, 2]]
Input 2: A = [2, 2, 2], B = [[0, 0], [1, 2]]

Example Output

Output 1: [10, 5]
Output 2: [2, 4]

Example Explanation

Explanation 1: The sum of all elements of A[0 … 3] = 1 + 2 + 3 + 4 = 10.
The sum of all elements of A[1 … 2] = 2 + 3 = 5.
Explanation 2: The sum of all elements of A[0 … 0] = 2 = 2.
The sum of all elements of A[1 … 2] = 2 + 2 = 4.

Brute Force Method

To calculate the sum for each query and the time complexity for that would be O(n*q)

For q queries, we’re traversing n elements in the worst case each time

Optimised: Prefix Sum

Preprocess the array to store prefix sums.

function rangeSumQuery(A, B){
 let prefixSum = findPrefixSum(A);
 let opArray = [];
 for(let i=0; i< B.length; i++){
 let l = B[i][0];
 let r = B[i][1];
 if(l === 0){
 opArray.push(prefixSum[r]);
 }else{
 opArray.push(prefixSum[r]-prefixSum[l-1]);
 }
 }
 return opArray;
}

function findPrefixSum(arr){
 let ps =[];
 for(let i=0; i< arr.length;i++){
 if(i==0){
 ps[i] = arr[i];
 }else{
 ps[i] = ps[i-1] + arr[i];
 }
 }
 return ps;
}
console.log(rangeSumQuery([1, 2, 3, 4, 5],[[0, 3]]));

Output: [10, 5]
⏱️ Time Complexity: O(N + Q)
📦 Space: O(N)

Quick Challenge

If A = [2, 2, 2] and B = [[0, 0], [1, 2]],
What’s the output?

Key Takeaways

  • Contribution Technique → understand element participation.
  • Prefix Sum → preprocess once, answer fast.
  • These are the building blocks for problems like sliding windows and segment trees.

At Dev Simplified, We Value Your Feedback 📊

👉 Follow us to not miss any updates.

👉 Have any suggestions? Let us know in the comments!

👉 Subscribe for free and join our growing community!