백준 1275번 [커피숍2](C++)-yes6686- 티스토리

백준 문제 풀이: 1275 [커피숍2]

---

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

문제 설명:

주어진 배열에서 구간 합을 빠르게 구하고, 특정 위치의 값을 변경할 수 있는 세그먼트 트리를 구현하여 질의에 응답하는 문제입니다.

---

문제 해결 코드

#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, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    go(1, 0, n - 1);
    int x, y, a, b;
    for (int i = 0; i < q; i++) {
        cin >> x >> y >> a >> b;
        if (x > y) {
            int temp = x;
            x = y;
            y = temp;
        }
        cout << sum(1, 0, n - 1, x - 1, y - 1) << '\n';
        long long int di = b - arr[a - 1];
        arr[a - 1] = b;
        change(1, 0, n - 1, a - 1, di);
    }
}

---

코드 설명

• 핵심 알고리즘: 세그먼트 트리를 사용하여 배열의 구간 합과 값 변경을 효율적으로 처리합니다.
• 구현 세부사항:
  • go 함수: 세그먼트 트리를 초기화하여 배열의 구간 합을 계산합니다.
  • sum 함수: 주어진 구간 [l, r]의 합을 반환합니다.
  • change 함수: 특정 위치 i의 값을 변경하고, 이에 따라 세그먼트 트리를 갱신합니다.
• 시간 복잡도: O(log n) per query
  • 세그먼트 트리 초기화: O(n)
  • 구간 합 및 값 변경: O(log n)

---

결과

세그먼트 트리를 사용하여 배열의 구간 합과 값 변경을 효율적으로 처리할 수 있습니다. 이 코드는 높은 성능을 요구하는 문제에 적합하며, 다양한 데이터 질의 문제에 응용할 수 있습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!