如何在恒定时间内从给定的索引间隔（i，j）中找到元素的总和？ [英] How to find sum of elements from given index interval (i, j) in constant time?

问题描述

给出一个数组。如何在恒定时间内找到索引间隔（i，j）中的元素总和。允许您使用多余的空间。

示例：

答：3 2 4 7 1 -2 8 0 -4 2 1 5 6 -1

长度= 14

Given an array. How can we find sum of elements in index interval (i, j) in constant time. You are allowed to use extra space.
Example:
A: 3 2 4 7 1 -2 8 0 -4 2 1 5 6 -1
length = 14

int getsum(int* arr, int i, int j, int len);
// suppose int array "arr" is initialized here
int sum = getsum(arr, 2, 5, 14);

总和在恒定时间内应为10。

sum should be 10 in constant time.

推荐答案

如果您可以花费O（n）时间来准备辅助信息，则可以基于该信息来计算O（1）中的总和，您可以轻松地做到这一点。

If you can spend O(n) time to "prepare" the auxiliary information, based on which you would be able calculate sums in O(1), you could easily do it.

准备（O（n））：

aux[0] = 0;
foreach i in (1..LENGTH) {
  aux[i] = aux[i-1] + arr[i];
}

查询（O（1））， arr 从 1 计算为 Length ：

Query (O(1)), arr is numerated from 1 to LENGTH:

sum(i,j) = aux[j] - aux[i-1];

我认为这是目的，因为否则，这是不可能的：对于任何 length 来计算 sum（0，length-1），您应该已经扫描了整个数组；至少需要线性时间。

I think it was the intent, because, otherwise, it's impossible: for any length to calculate sum(0,length-1) you should have scanned the whole array; this takes linear time, at least.

这篇关于如何在恒定时间内从给定的索引间隔（i，j）中找到元素的总和？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！