题目
输入样例:
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例:
3
6
10
算法1 O(n)
1、如何求Si Si = a1 + a2 + 、、、ai
2、Si的作用快速求数组的一段和
def Sn(n,num):
S = [0]*(n+1)
for i,x in enumerate(num):
S[i+1]=S[i]+x
return S
# Si-j = Sj-Si-1
if __name__=="__main__":
n,m=[int(i) for i in input().split()]
nums = [int(i) for i in input().split()]
#1、求和公式
Sn = Sn(n,nums)
ans = []
for _ in range(m):
i,j=[int(i) for i in input().split()]
ans.append(Sn[j]-Sn[i-1])#2、利用求和公式求段和
print('\n'.join(map(str,ans)))