给定一个大小为 n 的整数数组 arr。我们需要计算从索引 i 到索引 j 的元素之和。包含 i 和 j 索引值的查询将被执行多次。
示例：
> 输入 : arr[] = {1, 2, 3, 4, 5}
> i = 1, j = 3
> i = 2, j = 4
> 输出 : 9
> 12
> 输入 : arr[] = {1, 2, 3, 4, 5}
> i = 0, j = 4
> i = 1, j = 2
> 输出 : 15
> 5
[朴素解法] – 简单求和 – 每次查询 O(n) 时间复杂度，O(1) 空间复杂度
一个简单的解决方案是为每一个查询计算总和。
C++14
“// C++ program to find sum between two indexes
#include
using namespace std;
// Function to compute sum in given range
int rangeSum(const vector& 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 arr = { 1, 2, 3, 4, 5 };
cout << rangeSum(arr, 1, 3) << endl;
cout << rangeSum(arr, 2, 4) << endl;
return 0;
}
CODEBLOCK_0a9bccc8public 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));
}
}
CODEBLOCK_d3ce1d6c# 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));
CODEBLOCK_4e6ad6d3using 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));
}
}
CODEBLOCK_8fefd683function 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));
CODEBLOCK_3a048363
9
12
CODEBLOCK_0ea2c799#include
using namespace std;
void preCompute(vector& arr, vector& 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& pre)
{
if (i == 0)
return pre[j];
return pre[j] - pre[i - 1];
}
// Driver code
int main()
{
vector arr = { 1, 2, 3, 4, 5 };
vector pre(arr.size());
// Function call
preCompute(arr, pre);
cout << rangeSum(1, 3, pre) << endl;
cout << rangeSum(2, 4, pre) << endl;
return 0;
}
CODEBLOCK_0b95cb82// 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));
}
}
CODEBLOCK_d66cb1c9# 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)):
“