python - 对于给定的问题，以下两个代码的执行时间为什么会有如此大的差异？

题：
您将得到一个由n个数字和q个查询组成的数组。对于每个查询，您必须从L到R打印子数组的期望值（均值）的下限。

输入：

第一行包含两个整数N和Q，分别表示数组元素的数量和查询的数量。

下一行包含N个以空格分隔的整数，表示数组元素。

接下来的Q行包含两个整数L和R（数组的索引）。

输出：

打印一个表示答案的整数。

：

1
1
样本输入：

样本输出：

2
3
3

CODE1：

n,q=map(int, input().split())

arr=list(map(int,input().split()))
for i in range(0,q):
    s=0
    b=input().split()
    L=int(b[0])-1
    R=int(b[1])-1
    d=R-L+1
    for j in range(L,R+1):
        s=s+arr[j]
    print(s//d)

代码1的执行时间为8.02秒。

CODE2：

m, n = map(int, input().split())
a = list(map(int, input().split()))
s = []
s1 = 0
for i in range(m):
    s1 += a[i]
    s.append(s1)
for i in range(n):
    x, y = map(int, input().split())
    if x == 1:
        print((s[y-1])//(y-x+1))
    else:
        print((s[y-1] - s[x-2])//(y-x+1))

而CODE2仅需3.1秒即可执行。为什么呢？
请详细说明。

problem link

最佳答案

这是因为在代码1中：您正在计算l和r之间的每个值的平均值。
通过对k个查询执行此操作，您每次都会计算总和，然后求平均值。因此您的复杂度变为（k个查询*求和/均值的复杂度）

在代码2中：

您将连续的和保存在数组O（n）中

当计算k个查询的平均值时，您要从该求和数组中调用和值直到l和r元素，然后求和并计算平均值，因此每个查询的o（1）。为您节省时间。

关于python - 对于给定的问题，以下两个代码的执行时间为什么会有如此大的差异？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58264131/