[C++] 백준/Gold/2042. 구간 합 구하기

문제: 구간 합 구하기 (백준 2042번)

이번 문제는 직접 모든 구간을 계산하면 당연히 시간초과가 발생하고 세그먼트 트리를 이용해 $O(\log N)$시간 안에 구간 합을 구하는 문제이다.

---

우선 전역으로 세그먼트 트리와 원본 배열을 tree와 v의 이름으로 선언하고 n의 입력값에 따라 resize를 한다.

MakeTree

long long MakeTree(int start, int end, int node) {
    if (start == end) return tree[node] = v[start];
    int mid = (start + end) >> 1;
    int next = node << 1;
    return tree[node] = MakeTree(start, mid, next) + MakeTree(mid + 1, end, next + 1);
}

역할:

• MakeTree 함수는 주어진 배열 v를 기반으로 세그먼트 트리를 구축하는 역할을 한다.

동작 원리:

1. 기저 조건:
   • start == end인 경우, 즉 리프 노드이면 해당 인덱스의 값을 세그먼트 트리의 해당 노드에 저장하고 반환한다.
2. 분할 정복:
   • 배열을 중간 인덱스에서 분할한 후, 좌측 부분과 우측 부분의 합을 구해 현재 노드에 저장한다.
3. 재귀 호출:
   • 왼쪽 자식은 인덱스 node << 1, 오른쪽 자식은 node << 1 | 1 (여기서는 next + 1)으로 저장한다.

Sum

long long Sum(int start, int end, int node, int left, int right) {
    if (left > end || right < start) return 0;
    if (left <= start && right >= end) return tree[node];
    int mid = (start + end) >> 1;
    int next = node << 1;
    return Sum(start, mid, next, left, right) + Sum(mid + 1, end, next + 1, left, right);
}

역할:

• Sum 함수는 구간 [left,right][left, right]의 합을 계산하는 함수이다.

동작 원리:

1. 겹치지 않는 경우:
   • 요청 구간이 현재 구간 [start,end][start, end]와 전혀 겹치지 않으면 0을 반환한다.
2. 완전히 포함하는 경우:
   • 요청 구간이 현재 구간을 완전히 포함하면, 해당 노드의 값을 반환한다.
3. 부분적으로 겹치는 경우:
   • 배열을 반으로 나누어 재귀적으로 양쪽 구간의 합을 구해 반환한다.

Update

void Update(int start, int end, int node, int target, long long diff) {
    if (target < start || target > end)return;
    tree[node] += diff;
    if (start == end)return;
    int mid = (start + end) >> 1;
    int next = node << 1;
    Update(start, mid, next, target, diff);
    Update(mid + 1, end, next + 1, target, diff);
}

역할:

• Update 함수는 원본 배열의 특정 인덱스 target의 값을 변경할 때, 그 차이 diff를 반영하여 세그먼트 트리의 값을 갱신한다.

동작 원리:

1. 타겟 범위 검사:
   • target이 현재 노드의 구간 [start,end][start, end]에 속하지 않으면 함수를 종료한다.
2. 현재 노드 업데이트:
   • 현재 노드의 값을 diff만큼 더한다.
3. 리프 노드 검사:
   • 만약 start == end이면 리프 노드이므로 업데이트 후 종료.
4. 재귀 호출:
   • 타겟이 속한 구간으로 재귀적으로 들어가 업데이트를 수행한다.

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, k; cin >> n >> m >> k;
    tree.resize(n * 4);
    v.resize(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    MakeTree(0, n - 1, 1);
    for (int i = 0; i < m + k; i++) {
        int a, b; cin >> a >> b;
        long long c; cin >> c;
        if (a == 1) {
            long long diff = c - v[b - 1];
            v[b - 1] = c;
            Update(0, n - 1, 1, b - 1, diff);
        }
        else cout << Sum(0, n - 1, 1, b - 1, c - 1) << '\n';
    }
}

입력 처리:

• 배열의 크기 n, 수정 쿼리 m, 구간 합 쿼리 k를 입력받고, 원본 배열 v를 초기화한다.

세그먼트 트리 구축:

• MakeTree 함수를 호출하여 v를 기반으로 세그먼트 트리를 생성한다.

쿼리 처리:

• 쿼리 유형에 따라 두 가지 작업을 수행한다.
  • 업데이트 쿼리 (a == 1):
    • 원소 값을 업데이트하고, 그 차이를 Update 함수로 반영한다.
  • 구간 합 쿼리 (a != 1):
    • Sum 함수를 호출하여 지정된 구간의 합을 출력한다.