![[11659] 구간합 구하기4 (합배열)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F6fEMC%2Fbtsg1bkkEUq%2FwXfKz2k5bo3Vv35yLr0UhK%2Fimg.png)
728x90
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
분석
- 합 배열 공식 : S[i] = S[i-1] + A[i], 구간합 공식 : S[j] - S[i-1]
- 세그먼트 트리 : 2023.03.23 - [Algorithm PS/Tree] - 세그먼트 트리, 인덱스 트리, 구간합
풀이
import sys
input=sys.stdin.readline
n,k = map(int, input().split())
list = list(map(int, input().split()))
# 구간합 배열
sumList = [0]
temp = 0
for i in list:
temp += i
sumList.append(temp)
# 줄의 합을 구해야 하는 구간 s,e
for i in range(k):
s, e = map(int, input().split())
print(sumList[e]-sumList[s-1])
728x90