← 2주차 · 배열: 1차원과 2차원
보통누적합배열

구간에 값 더하기

길이 n인 배열이 있고 모든 칸이 0으로 시작해요. 갱신 목록 updates가 주어지며, 각 갱신은 [l, r, v] 형태로 l번부터 r번까지(양끝 포함) 모든 칸에 v를 더하라는 뜻이에요.

모든 갱신을 끝낸 뒤의 배열을 반환해요.

갱신마다 구간을 직접 돌면 O(nm)이에요. 차분 배열을 쓰면 갱신 하나가 두 칸 수정으로 끝나요. diff[l] += v, diff[r + 1] -= v 를 기록해 두고, 마지막에 diff의 누적합을 구하면 그것이 답이에요. 3주차의 누적합을 거꾸로 쓰는 셈이에요.

예시

예시 1
입력
n = 5, updates = [[0, 2, 1], [1, 3, 2]]
출력
[1, 3, 3, 2, 0]
설명
첫 갱신으로 [1,1,1,0,0], 두 번째 갱신으로 1~3번 칸에 2가 더해져요.
예시 2
입력
n = 3, updates = []
출력
[0, 0, 0]
설명
갱신이 없으면 그대로예요.
예시 3
입력
n = 4, updates = [[0, 3, -2]]
출력
[-2, -2, -2, -2]

제한 사항

  • 1 ≤ n ≤ 100,000
  • 0 ≤ updates.length ≤ 100,000
  • 0 ≤ l ≤ r < n
  • -1,000 ≤ v ≤ 1,000
차분 배열의 길이를 n + 1로 잡으면 r이 마지막 칸일 때 diff[r + 1] 이 배열 밖으로 나가는 걱정을 하지 않아도 돼요. 마지막에 앞에서부터 누적해 더하면서 앞 n칸만 반환해요.
javascript
function rangeAdd(n, updates) {
  const diff = new Array(n + 1).fill(0);
  for (const [l, r, v] of updates) {
    diff[l] += v;
    diff[r + 1] -= v;
  }
  const out = new Array(n).fill(0);
  let running = 0;
  for (let i = 0; i < n; i++) {
    running += diff[i];
    out[i] = running;
  }
  return out;
}
이전 문제구간 합 구하기
다음 문제문자열 뒤집기
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.