[백준 11659] 구간 합 구하기

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

11659번: 구간 합 구하기 4

특정 구간의 합을 구하는 문제이다.

 

리스트 li가 있을때 li[i]에 처음부터 인덱스 i까지의 값을 모두 더한 값을 저장한다.

 

이렇게 계속 누적 합을 구한다면 구간 합을 빠르게 구할 수 있다.

 

예를 들어 두 번째부터 다섯 번째까지 구간 합을 구한다면 처음부터 다섯 번째까지의 합에서 처음부터 첫 번째까지의 합을 빼면 된다.

 

위의 정의에 의하면 li[5] - li[1]가 된다.

 

<전체 코드>

import sys
n, m = map(int, sys.stdin.readline().split())
li=list(map(int, sys.stdin.readline().split()))
li.insert(0, 0)
for i in range(1, n+1):
    li[i]+=li[i-1]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    print(li[b]-li[a-1])