[Baekjoon] 10999 – 구간 합 구하기 2

https://www.acmicpc.net/problem/10999

📖 문제 해석

이 문제는 배열에서 두 가지 연산을 효율적으로 처리해야 하는 상황을 다룹니다. 첫째는 특정 구간의 모든 원소에 동일한 값을 더하는 구간 업데이트이고, 둘째는 특정 구간의 원소들의 합을 구하는 구간 합 쿼리입니다.

예시를 통해 살펴보겠습니다. 배열 [1, 2, 3, 4, 5]가 있을 때, “3번째부터 4번째 원소에 6을 더하라”는 명령을 받으면 배열은 [1, 2, 9, 10, 5]가 됩니다. 이후 “2번째부터 5번째까지의 합을 구하라”고 하면 2 + 9 + 10 + 5 = 26을 출력해야 합니다.

문제의 핵심은 이러한 연산들이 빈번히 일어난다는 점입니다. N은 최대 100만, 업데이트와 쿼리 횟수는 각각 최대 1만 번까지 가능하므로 효율적인 알고리즘이 필수적입니다.

🧠 순진한 접근법과 그 한계

처음 이 문제를 접했을 때 가장 자연스러운 생각은 배열을 직접 관리하는 것입니다. 구간 업데이트가 필요하면 해당 구간을 순회하며 각 원소에 값을 더하고, 구간 합이 필요하면 다시 해당 구간을 순회하며 합을 계산하는 방식입니다.

이 접근법은 구현이 간단하고 직관적이지만, 치명적인 성능 문제를 안고 있습니다. 구간 업데이트의 시간 복잡도가 O(N)이고, 구간 합 쿼리도 O(N)입니다. 최악의 경우 매번 전체 배열을 순회해야 하므로, 총 연산 횟수가 2만 번일 때 전체 시간 복잡도는 O(N × (M + K)), 즉 O(10<sup>6</sup> × 2 × 10<sup>4</sup>) = O(2 × 10<sup>10</sup>)이 됩니다. 이는 약 200억 번의 연산으로, 일반적인 시간 제한 내에서는 절대 통과할 수 없는 수준입니다.

💡 돌파구: 지연 전파를 활용한 세그먼트 트리

순진한 접근법의 핵심 문제는 구간 업데이트 시 모든 원소를 개별적으로 처리한다는 점입니다. 하지만 생각해보면, 같은 구간의 모든 원소에 같은 값을 더하는 작업은 본질적으로 중복이 많은 연산입니다. 이런 중복을 제거할 수 있다면 훨씬 효율적인 알고리즘을 만들 수 있을 것입니다.

여기서 핵심 아이디어는 지연 전파(Lazy Propagation)를 활용한 세그먼트 트리입니다. 일반적인 세그먼트 트리는 구간 합을 O(log N) 시간에 구할 수 있지만, 구간 업데이트는 여전히 O(N log N) 시간이 걸립니다. 하지만 지연 전파 기법을 사용하면 구간 업데이트도 O(log N) 시간에 처리할 수 있습니다.

지연 전파의 핵심 아이디어는 “필요할 때까지 업데이트를 미루자”는 것입니다. 구간 업데이트 요청이 들어왔을 때 실제로 모든 리프 노드를 업데이트하는 대신, 해당 구간을 포함하는 내부 노드에 “나중에 업데이트할 값”을 저장해둡니다. 그리고 실제로 그 구간에 접근할 필요가 생겼을 때 비로소 업데이트를 수행하는 것입니다.

📘 지연 전파(Lazy Propagation)에 대하여
지연 전파는 세그먼트 트리에서 구간 업데이트를 효율적으로 처리하기 위한 기법입니다. 각 노드에 추가로 “지연 값(lazy value)”을 저장하여, 업데이트가 필요한 하위 구간에 대한 정보를 미루어 두었다가 실제 접근 시점에 전파합니다. 이를 통해 구간 업데이트의 시간 복잡도를 O(log N)으로 줄일 수 있습니다.

이 방식이 효과적인 이유는 트리의 구조적 특성 때문입니다. 세그먼트 트리에서 임의의 구간은 최대 O(log N)개의 노드로 분해될 수 있습니다. 따라서 구간 업데이트 시 이 노드들에만 지연 값을 설정하면 되고, 나중에 쿼리가 들어올 때 지연 값을 실제 값으로 전파하면 됩니다.

🔍 알고리즘 상세 동작 과정

구체적인 예시를 통해 알고리즘의 동작을 살펴보겠습니다. 초기 배열이 [1, 2, 3, 4, 5]이고, 다음과 같은 연산들을 수행한다고 가정해봅시다.

  1. 구간 [2, 4]에 3을 더하기
  2. 구간 [1, 3]의 합 구하기
  3. 구간 [3, 5]에 -1을 더하기
  4. 구간 [2, 5]의 합 구하기

초기 상태: 세그먼트 트리를 구성할 때, 각 리프 노드는 배열의 원소값을 가지고, 내부 노드는 자식들의 합을 저장합니다. 동시에 모든 노드의 지연 값은 0으로 초기화됩니다.

첫 번째 연산: 구간 [2, 4]에 3 더하기

  • 구간 [2, 4]를 담당하는 노드들을 찾습니다.
  • 해당 노드들의 지연 값에 3을 더합니다.
  • 실제 세그먼트 값은 아직 업데이트하지 않습니다.
  • 이 시점에서 배열은 여전히 [1, 2, 3, 4, 5]처럼 보이지만, 내부적으로는 지연 정보가 저장되어 있습니다.

두 번째 연산: 구간 [1, 3]의 합 구하기

  • 구간 [1, 3]에 해당하는 노드들을 방문합니다.
  • 각 노드를 방문할 때마다 먼저 지연 전파를 수행합니다.
  • 노드 2번(인덱스 2)에 지연 값 3이 있으므로, 이를 실제 값에 반영하고 자식들에게 전파합니다.
  • 최종적으로 1 + (2+3) + (3+3) = 12를 반환합니다.

세 번째 연산: 구간 [3, 5]에 -1 더하기

  • 다시 해당 구간의 노드들을 찾아 지연 값에 -1을 추가합니다.
  • 노드 3번에는 이미 지연 값 3이 있었는데, 여기에 -1이 더해져서 지연 값이 2가 됩니다.

네 번째 연산: 구간 [2, 5]의 합 구하기

  • 구간 [2, 5]의 노드들을 방문하면서 모든 지연 값을 전파합니다.
  • 최종 배열 상태는 [1, 5, 5, 3, 4]가 되고, 구간 [2, 5]의 합은 5 + 5 + 3 + 4 = 17입니다.

💻 소스 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX_N 1000000

int N, M, K;
long long seg[4*MAX_N];    <em>// 세그먼트 트리 배열: 각 노드는 해당 구간의 합을 저장</em>
long long lazy[4*MAX_N];   <em>// 지연 배열: 각 노드의 미처리된 업데이트 값을 저장</em>

<em>// 지연 전파 함수: 노드의 지연 값을 실제 값에 반영하고 자식들에게 전파</em>
void propagate(int node, int L, int R) {
   <em>// 현재 노드의 실제 값을 업데이트 (구간 크기만큼 곱해서 더함)</em>
   seg[node] += lazy[node] * (R - L + 1);
   
   <em>// 리프 노드가 아니라면 지연 값을 자식들에게 전파</em>
   if (L != R) {
      lazy[node*2] += lazy[node];      <em>// 왼쪽 자식에게 전파</em>
      lazy[node*2+1] += lazy[node];    <em>// 오른쪽 자식에게 전파</em>
   }
   
   <em>// 현재 노드의 지연 값은 처리 완료되었으므로 0으로 초기화</em>
   lazy[node] = 0LL;
}

<em>// 구간 업데이트 함수: [l, r] 구간에 값 v를 더함</em>
void update(int node, int l, int r, long long v, int L, int R) {
   <em>// 먼저 현재 노드의 지연 값을 전파</em>
   propagate(node, L, R);
   
   <em>// 업데이트 구간과 현재 노드 구간이 겹치지 않으면 종료</em>
   if (l > R || r < L) return;
   
   <em>// 현재 노드 구간이 업데이트 구간에 완전히 포함되면</em>
   if (l <= L && R <= r) {
      lazy[node] += v;           <em>// 지연 값에 v를 추가</em>
      propagate(node, L, R);     <em>// 즉시 전파하여 현재 노드 값 업데이트</em>
      return;
   }
   
   <em>// 부분적으로 겹치는 경우: 자식들을 재귀적으로 업데이트</em>
   int M = (L + R) / 2;
   update(node*2, l, r, v, L, M);        <em>// 왼쪽 자식 업데이트</em>
   update(node*2+1, l, r, v, M+1, R);   <em>// 오른쪽 자식 업데이트</em>
   
   <em>// 자식들의 값을 합하여 현재 노드 값 갱신</em>
   seg[node] = seg[2*node] + seg[2*node+1];
}

<em>// 구간 합 쿼리 함수: [l, r] 구간의 합을 반환</em>
long long query(int node, int l, int r, int L, int R) {
   <em>// 먼저 현재 노드의 지연 값을 전파</em>
   propagate(node, L, R);
   
   <em>// 쿼리 구간과 현재 노드 구간이 겹치지 않으면 0 반환</em>
   if (l > R || r < L) return 0LL;
   
   <em>// 현재 노드 구간이 쿼리 구간에 완전히 포함되면 노드 값 반환</em>
   if (l <= L && R <= r) {
      return seg[node];
   }
   
   <em>// 부분적으로 겹치는 경우: 자식들의 결과를 합산</em>
   int M = (L + R) / 2;
   long long left = query(node*2, l, r, L, M);      <em>// 왼쪽 자식 쿼리</em>
   long long right = query(node*2+1, l, r, M+1, R); <em>// 오른쪽 자식 쿼리</em>
   
   return left + right;
}

int main() {
   <em>// 입출력 최적화</em>
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   
   <em>// 배열 초기화: 모든 값을 0으로 설정</em>
   memset(seg, 0LL, sizeof(seg));
   memset(lazy, 0LL, sizeof(lazy));
   
   <em>// 입력 받기</em>
   cin >> N >> M >> K;
   
   long long v, a, b, c, d;
   
   <em>// 초기 배열 값들을 세그먼트 트리에 삽입</em>
   for (int i = 1; i <= N; ++i) {
      cin >> v;
      update(1, i, i, v, 1, N);  <em>// 각 위치에 개별 업데이트</em>
   }
   
   <em>// M번의 업데이트와 K번의 쿼리 처리</em>
   for (int i = 0; i < M + K; ++i) {
      cin >> a;
      
      if (a == 1) {
         <em>// 구간 업데이트: b번째부터 c번째까지 d를 더함</em>
         cin >> b >> c >> d;
         update(1, b, c, d, 1, N);
      } else {
         <em>// 구간 합 쿼리: b번째부터 c번째까지의 합을 출력</em>
         cin >> b >> c;
         cout << query(1, b, c, 1, N) << "\n";
      }
   }
   
   return 0;
}

📌 핵심 아이디어와 교훈

이 문제에서 가장 중요한 통찰은 “모든 업데이트를 즉시 처리할 필요가 없다”는 것입니다. 지연 전파 기법을 통해 업데이트를 미루어두고 실제 필요한 시점에만 처리함으로써, 구간 업데이트의 시간 복잡도를 획기적으로 줄일 수 있었습니다.

세그먼트 트리와 지연 전파의 조합은 구간 쿼리와 구간 업데이트가 모두 빈번한 상황에서 매우 강력한 도구입니다. 단순한 배열 기반 접근법으로는 해결할 수 없는 대용량 데이터와 많은 연산 횟수를 O(log N) 시간에 처리할 수 있게 해줍니다.

이 알고리즘의 핵심은 트리 구조를 활용한 분할 정복과 지연 평가의 결합입니다. 복잡해 보이는 구간 연산을 로그 시간에 처리할 수 있는 이유는 세그먼트 트리의 균형 잡힌 구조와 지연 전파의 효율적인 업데이트 관리 덕분입니다.

Similar Posts