如何在恒定时间内从给定的索引间隔（i，j）中找到元素的总和？

本文介绍了如何在恒定时间内从给定的索引间隔（i，j）中找到元素的总和？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给出一个数组。如何在恒定时间内找到索引间隔（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.