Python Cho một dãy gồm N số nguyên dương AI,A2,...AN.(N< 105, Ai <10°). Cho Q truy vấn có dạng (u,v). Với mỗi truy vấn (uv) trả lời tổng các phần tử của mảng A từ phần tứ thứ u đến phần tử thứ v. Input: - Dòng đầu chứa số N, Q(1<Q<10°) - Dòng thứ hai chứa N số nguyên dương A1, A2,..., AN. Q dòng tiếp theo ghi 2 số nguyên u,v(1<u<v<10°) Output: Gồm Q dòng, mỗi dòng ghi trả lời tương ứng với mỗi truy vấn..

$\texttt{Python}$

$\texttt{2 for (Không tối ưu): }$

n, q = map(int, input().split())
a = list(map(int, input().split()))
for i in range(1,q+1):
  u, v = map(int, input().split())
  s=0
  for i in range(u-1,v): # Vì mảng ở đây bắt đầu từ 0 -> n-1
    s+=a[i]
  print(s);

$\texttt{Quy hoạch động (Tối ưu): }$

n, q = map(int, input().split())
a = list(map(int, input().split()))
l = [a[0]]
for i in range(1, n):
  l.append(l[i - 1] + a[i])
while q != 0:
  u, v = map(int, input().split())
  print(l[v - 1] - l[u - 2] if u > 1 else l[v - 1])
  q -= 1