개념만 알면 쉽다
그냥 리스트로 하면 O(mn) 이 된다.
참고로 행렬 m개에 대해 n번의 더하기를 수행한다는 뜻이다.
따라서, 누적합리스트를 생성한다.
그리고 구간이 주어지면, 끝구간의 값에서 시작구간 값-1을 해주면 된다
import sysinput=sys.stdin.readlinel=[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])