Range sum queries without updates

Last Updated : 06 Mar, 2025

Given an array arr of integers of size n. We need to compute the sum of elements from index i to index j. The queries consisting of i and j index values will be executed multiple times.

Examples:

Input : arr[] = {1, 2, 3, 4, 5}
i = 1, j = 3
i = 2, j = 4
Output : 9
12
Input : arr[] = {1, 2, 3, 4, 5}
i = 0, j = 4
i = 1, j = 2
Output : 15
5

[Naive Solution] - Simple Sum - O(n) for Every Query and O(1) Space

A Simple Solution is to compute the sum for every query.

C++14

// C++ program to find sum between two indexes #include <bits/stdc++.h> using namespace std; // Function to compute sum in given range int rangeSum(const vector<int>& arr, int i, int j) {  int sum = 0;  // Compute sum from i to j  for (int k = i; k <= j; k++) {  sum += arr[k];  }  return sum; } // Driver code int main() {  vector<int> arr = { 1, 2, 3, 4, 5 };  cout << rangeSum(arr, 1, 3) << endl;  cout << rangeSum(arr, 2, 4) << endl;  return 0; }

Java

public class Main {    // Function to compute sum in given range  static int rangeSum(int[] arr, int i, int j) {  int sum = 0;  // Compute sum from i to j  for (int k = i; k <= j; k++) {  sum += arr[k];  }  return sum;  }  // Driver code  public static void main(String[] args) {  int[] arr = { 1, 2, 3, 4, 5 };  System.out.println(rangeSum(arr, 1, 3));  System.out.println(rangeSum(arr, 2, 4));  } }

Python

# Python3 program to find sum between two indexes # when there is no update. # Function to compute sum in given range def rangeSum(arr, i, j) : sum = 0; # Compute sum from i to j for k in range(i, j + 1) : sum += arr[k]; return sum; # Driver code if __name__ == "__main__" : arr = [ 1, 2, 3, 4, 5 ]; print(rangeSum(arr, 1, 3)); print(rangeSum(arr, 2, 4));

using System; public class RangeSumCalculator {  // Function to compute sum in the given range  public static int RangeSum(int[] arr, int i, int j)  {  int sum = 0;  // Compute sum from index i to j  for (int k = i; k <= j; k++)  {  sum += arr[k];  }  return sum;  }  public static void Main(string[] args)  {  int[] arr = { 1, 2, 3, 4, 5 };  Console.WriteLine(RangeSum(arr, 1, 3));  Console.WriteLine(RangeSum(arr, 2, 4));  } }

JavaScript

function GFG(arr, i, j) {  let sum = 0;  // Compute sum from i to j  for (let k = i; k <= j; k++) {  sum += arr[k];  }  return sum; } const arr = [ 1, 2, 3, 4, 5 ]; console.log(GFG(arr, 1, 3)); console.log(GFG(arr, 2, 4));

Output

9 12

[Expected Solution] - Prefix Sum - O(1) for Every Query and O(n) Space

Follow the given steps to solve the problem:

Create the prefix sum array of the given input array
Now for every query (1-based indexing)
- If L is greater than 1, then print prefixSum[R] - prefixSum[L-1]
- else print prefixSum[R]

C++

#include <bits/stdc++.h> using namespace std; void preCompute(vector<int>& arr, vector<int>& pre) {  pre[0] = arr[0];  for (int i = 1; i < arr.size(); i++)  pre[i] = arr[i] + pre[i - 1]; } // Returns sum of elements in arr[i..j] // It is assumed that i <= j int rangeSum(int i, int j, const vector<int>& pre) {  if (i == 0)  return pre[j];  return pre[j] - pre[i - 1]; } // Driver code int main() {  vector<int> arr = { 1, 2, 3, 4, 5 };  vector<int> pre(arr.size());    // Function call  preCompute(arr, pre);  cout << rangeSum(1, 3, pre) << endl;  cout << rangeSum(2, 4, pre) << endl;  return 0; }

Java

// Java program to find sum between two indexes // when there is no update. import java.util.*; import java.lang.*; class GFG {  public static void preCompute(int arr[], int pre[])  {  pre[0] = arr[0];  for (int i = 1; i < arr.length; i++)  pre[i] = arr[i] + pre[i - 1];  }  // Returns sum of elements in arr[i..j]  // It is assumed that i <= j  public static int rangeSum(int i, int j, int pre[])  {  if (i == 0)  return pre[j];  return pre[j] - pre[i - 1];  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 1, 2, 3, 4, 5 };  int pre[] = new int[arr.length];  preCompute(arr, pre);  System.out.println(rangeSum(1, 3, pre));  System.out.println(rangeSum(2, 4, pre));  } }

Python

# Function to precompute the prefix sum def pre_compute(arr): pre = [0] * len(arr) pre[0] = arr[0] for i in range(1, len(arr)): pre[i] = arr[i] + pre[i - 1] return pre # Returns sum of elements in arr[i..j] # It is assumed that i <= j def range_sum(i, j, pre): if i == 0: return pre[j] return pre[j] - pre[i - 1] # Driver code arr = [1, 2, 3, 4, 5] pre = pre_compute(arr) print(range_sum(1, 3, pre)) print(range_sum(2, 4, pre))

// C# program to find sum between two indexes using System; class GFG {  public static void PreCompute(int[] arr, int[] pre)  {  pre[0] = arr[0];  for (int i = 1; i < arr.Length; i++)  pre[i] = arr[i] + pre[i - 1];  }  // Returns sum of elements in arr[i..j]  // It is assumed that i <= j  public static int RangeSum(int i, int j, int[] pre)  {  if (i == 0)  return pre[j];  return pre[j] - pre[i - 1];  }  // Driver code  public static void Main(string[] args)  {  int[] arr = { 1, 2, 3, 4, 5 };  int[] pre = new int[arr.Length];  PreCompute(arr, pre);  Console.WriteLine(RangeSum(1, 3, pre));  Console.WriteLine(RangeSum(2, 4, pre));  } }

JavaScript

// Function to precompute the prefix sum function preCompute(arr) {  let pre = new Array(arr.length).fill(0);  pre[0] = arr[0];  for (let i = 1; i < arr.length; i++) {  pre[i] = arr[i] + pre[i - 1];  }  return pre; } // Returns sum of elements in arr[i..j] // It is assumed that i <= j function rangeSum(i, j, pre) {  if (i === 0) {  return pre[j];  }  return pre[j] - pre[i - 1]; } // Driver code let arr = [1, 2, 3, 4, 5]; let pre = preCompute(arr); console.log(rangeSum(1, 3, pre)); console.log(rangeSum(2, 4, pre));

Output

9 12

Here time complexity of every range sum query is O(1) and the overall time complexity is O(n).

Auxiliary Space required = O(n), where n is the size of the given array.

The question becomes complicated when updates are also allowed. In such situations when using advanced data structures like Segment Tree or Binary Indexed Tree.