[BOJ] 11659. 구간 합 구하기 4

📌 문제 제목

문제 링크: BOJ 11659

---

🗒️ 문제 설명

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램

시간 제한: 1초

메모리 제한 256MB

1 <= N <= 100,000

1 <= M <= 100,000

1 <= i <= j <= N

e.g.
입력
5 3 # N과 M (N: 수의 개수, M: 합을 구해야 하는 횟수)
5 4 3 2 1 (수열 N)
1 3 (i, j)
2 4 (i, j)
5 5 (i, j)

출력
12 (5 + 4 + 3)
9 (4 + 3 + 2)
1 (1)

---

💡 문제 해결 아이디어

• N과 M이 최대 100,000이기 때문에 시간 복잡도 O(N log N)의 알고리즘 필요
• i부터 j까지의 합은 1부터 j까지의 합 - 1부터 i-1 까지의 합
• 테이블 정의
  • dp[i]는 1번째 값부터 i번째 까지의 합
• 점화식 찾기
  • dp[i] = dp[i-1] + seq[i]

---

⌛️ 시간 복잡도

• O(N+M)

---

✅ 최종 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
n_seq = list(map(int, input().split()))

dp = [0] + [-1] * N
for i, val in enumerate(n_seq):
    dp[i + 1] = dp[i] + val

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