보통누적합배열

구간 합 구하기

정수 배열 nums와 질문 목록 queries가 주어져요. 각 질문은 [l, r] 형태이고, nums[l] 부터 nums[r] 까지(양끝 포함)의 합을 뜻해요. 질문마다의 답을 순서대로 배열에 담아 반환해요.

질문이 들어올 때마다 l부터 r까지 더하면 질문 하나가 O(n)이고, 질문이 10만 개면 O(nq)가 되어 늦어요.

누적합을 미리 만들어 두면 각 질문은 뺄셈 한 번이에요. pre[i] 를 앞에서부터 i개의 합이라고 두면, l..r 의 합은 pre[r + 1] - pre[l] 이에요. 길이를 n + 1로 잡는 이유는 l = 0 일 때 따로 처리하지 않으려는 거예요.

예시

예시 1

입력: nums = [1, 2, 3, 4, 5], queries = [[0, 2], [1, 3], [4, 4]]
출력: [6, 9, 5]
설명: 1+2+3 = 6, 2+3+4 = 9, 5 = 5 예요.

예시 2

입력: nums = [10], queries = [[0, 0]]
출력: [10]

제한 사항

1 ≤ nums.length ≤ 100,000
1 ≤ queries.length ≤ 100,000
0 ≤ l ≤ r < nums.length
-10^6 ≤ nums[i] ≤ 10^6

누적합 배열을 pre[0] = 0, pre[i + 1] = pre[i] + nums[i] 로 만들어요. 그러면 질문 하나는 pre[r + 1] - pre[l] 로 끝나요. r + 1 을 쓰기 때문에 배열 길이는 n + 1 이어야 해요.

javascript
Copy code
function rangeSum(nums, queries) {
  const pre = new Array(nums.length + 1).fill(0);
  for (let i = 0; i < nums.length; i++) pre[i + 1] = pre[i] + nums[i];
  return queries.map(([l, r]) => pre[r + 1] - pre[l]);
}

이전 문제행의 합이 가장 큰 줄

다음 문제구간에 값 더하기

예시 테스트만 실행 (Cmd/Ctrl+Enter)

숨김 테스트까지 채점 (Cmd/Ctrl+Shift+Enter)

에디터를 불러오고 있어요…

코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.