题目描述
开始暴力求解,直接用for循环依次相加处理,但是超时了,所以在看了视频之后选择了前缀和的方式。前缀和适用于连续区域的求和,可以通过相加每一项,然后相减的方式提高算法效率。
样例
blablabla
n,m=map(int,input().split())
nums=[0]+list(map(int,input().split()))
for i in range(1,n+1):
nums[i]+=nums[i-1]
for i in range(m):
l,r=map(int,input().split())
print(nums[r]-nums[l-1])
算法2
(暴力枚举) $O(n^2)$
for i in range(m):
xunwen=list(map(int,input().split()))
ans=0
for j in range(xunwen[0]-1,xunwen[1]):
ans=nums[j]+ans
print(ans)
python 代码
blablabla