백준 2042번 [구간 합 구하기](C++)-yes6686- 티스토리

백준 문제 풀이: 2042 [구간 합 구하기]

---

문제 링크: https://www.acmicpc.net/problem/2042

문제 설명:

길이가 n인 수열이 주어졌을 때, 다음 두 가지 연산을 효율적으로 처리해야 합니다:

• 구간 합 계산: 수열의 특정 구간에 속하는 원소들의 합을 구합니다.
• 값 변경: 수열의 특정 원소 값을 변경합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

long long int arr[1000001];
long long int seg[4000001];

long long int go(int n, int s, int e) {
    if (s == e) {
        return seg[n] = arr[s];
    } else {
        int mid = (s + e) / 2;
        long long int left = go(2 * n, s, mid);
        long long int right = go(2 * n + 1, mid + 1, e);
        seg[n] = left + right;
        return seg[n];
    }
}

long long int sum(int n, int s, int e, int l, int r) {
    if (e < l || r < s) return 0;
    if (l <= s && r >= e) {
        return seg[n];
    }
    int mid = (s + e) / 2;
    long long int left = sum(n * 2, s, mid, l, r);
    long long int right = sum(n * 2 + 1, mid + 1, e, l, r);
    return left + right;
}

void change(int n, int s, int e, int i, long long int d) {
    if (i < s || i > e) return;
    seg[n] += d;
    if (s != e) {
        int mid = (s + e) / 2;
        change(n * 2, s, mid, i, d);
        change(n * 2 + 1, mid + 1, e, i, d);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    go(1, 0, n - 1);
    long long int a, b, c;
    for (int i = 0; i < m + k; i++) {
        cin >> a >> b >> c;
        if (a == 1) {
            long long int di = c - arr[b - 1];
            arr[b - 1] = c;
            change(1, 0, n - 1, b - 1, di);
        } else if (a == 2) {
            cout << sum(1, 0, n - 1, b - 1, c - 1) << '\n';
        }
    }
}

---

코드 설명

• 세그먼트 트리 초기화: 함수 go는 입력 배열을 기반으로 세그먼트 트리를 생성합니다.
• 구간 합 계산: 함수 sum은 특정 구간의 합을 계산합니다.
• 값 변경: 함수 change는 특정 위치의 값을 변경하고 세그먼트 트리를 업데이트합니다.
• 시간 복잡도: 세그먼트 트리 초기화는 O(n), 각 쿼리는 O(log n)이며, m + k개의 쿼리를 처리하므로 총 시간 복잡도는 O(n + (m + k) log n)입니다.

---

결과

세그먼트 트리를 사용하여 구간 합 계산과 값 변경 문제를 효율적으로 해결했습니다. 더 나은 풀이 방법이나 질문이 있으면 댓글로 알려주세요!