구간합, 누적합 알고리즘

prefix_sum.py

# 기존 배열의 값을 입력받는다.
n_arr = list(map(int, input().split()))

# 누적합 배열을 초기화 한다.
p_arr = [0]
# 누적합을 하여 배열에 값을 넣는다.
for i in n_arr:
  p_arr.append(p_arr[-1] + i)

answers = []
M = int(input())
for _ in range(M):
  a, b = map(int, input().split())
  # a-1 번째 인덱스의 값을 b 번째 인덱스의 값과 뺄셈을 한다.
  # a번째 인덱스 값이 아닌 a-1번째 인덱스 값인 이유는 0_base index이기 때문이다.
  answers.append(p_arr[b] - p_arr[a-1])

for answer in answers:
  print(answer)