如何优化以下Python代码，以防止时间异常

Question

每个人。我写了以下代码。请帮助我，为了优化这一点，当我在一些测试用例中提交编译器写入时间限制超过2.069s/13.33Mb时。

import math
N = int(input())
arr = [None]*N; new_list = []
stepen = 0; res = .0;
arr = input().split(" ")
arr = [float(h) for h in arr]
Q = int(input())

for j in range(Q):
x, y = input().split()
new_list.extend([int(x), int(y)])

for i, j in zip(new_list[0::2], new_list[1::2]):
stepen = (j - i)+ 1
res = math.prod(arr[i:j+1])
print(pow(res, 1./stepen))

Answer 1

算法中最慢的是math.prod(arr[i:j+1])。如果所有的x和y输入都表示整个范围，那么您肯定会TLE，因为对prod的调用必须在整个范围内循环。

为了避免这种情况，您必须在阵列上执行前缀乘积。其想法是：保留第二个数组pref，属性为pref[i] = arr[i] * pref[i-1]。因此，pref[i]将是arr中i位置和之前的所有内容的乘积。

然后要查找位置i和j之间的乘积，您需要pref[j] / pref[i-1]。看看你是否能弄清楚为什么这个答案是正确的。