구간 합 계산

구간 합 문제란 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구한느 문제를 말한다.

가장 많이 사용되는 기법-> 접두사의 합(Prefix_sum)
접두사합이란 리스트의 맨 앞부터 특정 위치까지의 합을 구해 놓은 것을 의미한다.

알고리즘 ->
1. N개의 수에 대하여 접두사 합(Prefix sum)을 계산하여 배열 P에 저장한다.
2. 매 M개의 쿼리 정보[L,R]을 확인할 떄, 구간 합은 P[R]-P[L-1]이다.

• 시간 복잡도는 O(N+M)이다

   
   n= 5
  		data = [10, 20, 30, 40, 50]
  
  #접두사 합(Prefix Sum)배열 계산
  sum_value = 0
  prefix_sum=[0]
  for i in data:
   sum_value+= i
   prefix_sum.append(sum_value)
  
  #구간 합 계싼(세 번쨰 수부터 네 번쨰 수까찌)
  
  left = 3 
  right=4
  print(prefix_sum[right]-prefix_sum[left-1])