(파이썬) 백준 11659번 "구간 합 구하기 4"

---

# 답

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = [0] + list(map(int, input().split()))

for i, v in enumerate(arr):
    if i != 0:
        arr[i] += arr[i - 1]

for _ in range(M):
    i, j = map(int, input().split())
    print(arr[j] - arr[i - 1])

 

 

 

 

---

# 원리

i번째부터 j번째까지의 구간 합을 빠르게 구하는 방법은

1) 주어진 배열을 처음부터 누적합 형태로 바꿔놓고,

2) arr[j] - arr[i - 1]하면 됩니다.

 

 

예를 들어, 다음과 같은 배열 arr1이 있다고 가정해봅시다.

arr1 = [1, 1, 1, 1, 1, 1]

 

그럼 arr1을 arr2와 같이 앞에서부터 값을 누적한 배열을 생성해줍니다.

arr2 = [1, 2, 3, 4, 5, 6]

 

arr1 배열의 1번째부터 3번째까지의 합은 아래와 같이 구할 수도 있지만,

arr1[1] + arr1[2] + arr1[3] = 3

 

이렇게 구하면 훨씬 빠릅니다.

arr2[3] - arr2[0] = 4 - 1 = 3