11659 구간합 구하기 4

개념만 알면 쉽다

그냥 리스트로 하면 O(mn) 이 된다.

참고로 행렬 m개에 대해 n번의 더하기를 수행한다는 뜻이다.

 

따라서, 누적합리스트를 생성한다.

그리고 구간이 주어지면, 끝구간의 값에서 시작구간 값-1을 해주면 된다

import sys
input=sys.stdin.readline

l=[0]
n,m=map(int,input().split())
t=[* map(int,input().split())]

for tt in t: 
    l.append(l[-1]+tt)


for _ in range(m):
    a,b=map(int,input().split())
    print(l[b]-l[a-1])