(Python) 백준 11659 - 구간 합 구하기 4

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

아이디어

• 최대 10만개의 쿼리가 주어지기 때문에 쿼리 마다 합을 구할 경우 시간 초과가 일어날 것이다.
• 합을 미리 구해서 조회하는 방식을 사용하면 쿼리당 O(1) 에 처리할 수 있다.
• prefix sum을 이용하여 배열의 모든 원소 k의 1번째 부터 k번째 원소의 합을 O(n)에 구할 수 있다.
• i번째 부터 j번째 원소의 합을 요청하는 쿼리가 주어졌을 때, 1번째 부터 j까지 합에서 1번째 부터 i-1번째의 합을 빼준 값을 출력한다.

 

코드

import sys
input=lambda:map(int,sys.stdin.readline().split())
n,m=input()
a=[0]+[*input()]
for i in range(1,n+1):a[i]+=a[i-1]
for _ in range(m): 
 i,j=input()
 print(a[j]-a[i-1])