Funcia
Lv.3fenwick-treelazy-propagationsegment-tree

구간에 더하고 구간 합 구하기

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

정수 배열 values와 명령 배열 ops가 주어집니다. 명령은 순서대로 처리하며, 두 종류가 있습니다.

  • [1, l, r, x]: values[l], values[l+1], …, values[r]에 모두 x를 더합니다.
  • [2, l, r]: values[l] + values[l+1] + … + values[r]를 구합니다.

2번 명령의 답을 나온 순서대로 배열에 담아 반환하세요.

입출력 예

valuesopsresult
[1, 2, 3, 4, 5][[2, 0, 4], [1, 1, 3, 10], [2, 0, 2], [2, 3, 4]][15, 26, 19]
[0, 0, 0][[1, 0, 2, -4], [1, 1, 1, 6], [2, 1, 2], [2, 0, 0]][-2, -4]

입출력 예 설명

예 1 — 처음 전체 합은 15입니다. 1~3번 칸에 10을 더하면 배열이 [1, 12, 13, 14, 5]가 되어 [0, 2] 구간 합은 26, [3, 4] 구간 합은 19입니다.

예 2 — 두 명령 뒤 배열은 [-4, 2, -4]입니다. [1, 2] 구간 합은 2 + (-4) = -2, [0, 0]은 -4입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(values: int[], ops: int[][]) → long[]

제한 사항

  • 1≤N=1 \le N = values.length ≤100,000\le 100{,}000
  • 1≤Q=1 \le Q = ops.length ≤100,000\le 100{,}000
  • −109≤-10^9 \le values[i] ≤109\le 10^9, −106≤-10^6 \le x ≤106\le 10^6
  • 모든 명령에서 0≤0 \le l ≤\le r <N< N
  • 2번 명령은 적어도 하나 있습니다. 합은 32비트 정수를 넘을 수 있지만 64비트 정수 범위 안입니다.

기대 복잡도

시간
O((N + Q) log N)
공간
O(N)

입출력 예

valuesops기대 출력
[1,2,3,4,5][[2,0,4],[1,1,3,10],[2,0,2],[2,3,4]][15,26,19]
[0,0,0][[1,0,2,-4],[1,1,1,6],[2,1,2],[2,0,0]][-2,-4]

힌트

힌트

구간에 더하는 명령을 칸마다 처리하면 한 번에 O(N)O(N)이 듭니다. **구간 갱신과 구간 합을 모두 O(log⁡N)O(\log N)**에 하는 방법이 필요합니다.

1. 지연 전파 세그먼트 트리 — 노드마다 "구간 합"과 "아직 자식에게 내려보내지 않은 덧셈 값(lazy)"을 둡니다. 갱신 구간이 노드 구간을 완전히 덮으면 그 노드의 합에 x × 길이를 더하고 lazy에만 기록한 뒤 멈춥니다. 나중에 그 노드의 자식을 내려가야 할 때 lazy를 자식에게 넘겨 줍니다.

2. 펜윅 트리 두 개 — 차분 배열 d(d[l] += x, d[r+1] -= x)를 생각하면 앞쪽 i칸의 합은 ∑j≤idj⋅(i−j+1)\sum_{j \le i} d_j \cdot (i - j + 1) 입니다. 이를 (i+1)∑dj−∑dj⋅j(i+1)\sum d_j - \sum d_j \cdot j 로 나누어, d_j와 d_j · j를 각각 펜윅 트리에 담으면 됩니다.

합은 반드시 64비트 정수로 다루세요.

복잡도 목표

명령마다 구간을 직접 돌면서 더하거나 합하는 O(NQ)O(NQ) 풀이는 효율성 테스트에서 시간 초과가 납니다. O((N+Q)log⁡N)O((N + Q)\log N)이 필요합니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251916 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample02입력·출력 공개
correctness4012판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.