Static Range Sum Queries

前綴和會使時間複雜度變：

建立前綴和：O(n)

回答每筆查詢：O(1)

所以總時間：O(n + q)

但是python I/O過慢會導致超時，所以可以在前面

import sys
input = sys.stdin.readline

加速input

import sys
input = sys.stdin.readline

n,q = map(int,input().split())
li = list(map(int, input().split()))
p = [0] * (n + 1)
for i in range(1,n+1):
    p[i] = p[i - 1] + li[i - 1]

for _ in range(q):
    l,r = map(int, input().split())
    print(p[r] - p[l - 1])

前綴和可參考：https://hackmd.io/@HyC-1029/By-o9OAoyg