优化列表范围内的数字和

Question

我正在试着回答一个关于在线裁判的问题，但是我总是遇到时间限制的问题。这个问题的主要思想是求解一个列表的和减去该列表中的子列表的和。完整的问题规范可以在这里看到。

下面是我的代码:

import sys
lists = sys.stdin.read().strip().split('n')
showScores = map(int, lists[1].split())
maximum = sum(showScores)
loops = map(int, lists[0].split())[1]
for i in range(2, loops+2):
    subList = lists[i].split()
    print maximum - sum(showScores[int(subList[0])-1 : int(subList[1])])

是否有更好的算法来解决这个问题?考虑到我要做多达50万个循环，我该怎么做呢?

Answer 1

您可以避免为每个查询调用sum。无论切片的效率有多高，在当前设置下，您仍然需要迭代该范围以计算其总和。所以你需要优化你的算法，而不是代码。

如果你有:

S[i] = sum of the first i numbers
     = a[0] + a[1] + ... + a[i]

可以在O(n)中计算:

S[i] = S[i - 1] + a[i]

如何用S来回答O(1)中的每个查询?

提示:如果您必须计算某个区间[x, y]的和，我们将使用:

S[y] = a[0] + a[1] + ... + a[x] + ... + a[y]
S[x] = a[0] + a[1] + ... + a[x - 1] + a[x]

Answer 2

@IVlad在他的回答中给出了一个非常有用的提示，我将通过示例进一步说明。只要在循环之前预先计算值，循环执行的速度就会越快。在一个slice上运行sum()将每次为相同的slice返回相同的值，因此在循环之前预先计算总和。

如果生成一个a首个得分之和的列表，它看起来像这样:

first = [0, 5, 11, 18, 26, 29, 33, 38, 44, 45, 47]

如果您还生成一个b最后得分之和的列表，它看起来像这样:

last = [47, 42, 36, 29, 21, 18, 14, 9, 3, 2, 0]

在循环中，你可以

print first[a-1] + last[b]

比取切片和要快。