[11659] 구간합 구하기4 (합배열)

11659번: 구간 합 구하기 4

 

분석

• 합 배열 공식 : 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])