백준 2268번 [수들의 합 7](C++)-yes6686- 티스토리

백준 문제 풀이: 2268 [수들의 합 7]

---

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

문제 설명:

1부터 N까지 번호가 매겨진 배열의 값을 갱신하거나, 특정 구간의 합을 구하는 작업을 효율적으로 수행하는 문제입니다. 세그먼트 트리를 사용하여 O(log n) 시간 복잡도로 각 작업을 처리합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[1000001];
long long int t[3000001];

long long int sum(int n, int s, int e, int l, int r) {
    if (r < s || l > e) return 0;
    if (l <= s && e <= r) return t[n];

    return sum(n * 2, s, (s + e) / 2, l, r) + sum(n * 2 + 1, (s + e) / 2 + 1, e, l, r);
}

void modify(int n, int s, int e, int i, int diff) {
    if (i < s || e < i) return;
    t[n] += diff;
    if (s != e) {
        modify(2 * n, s, (s + e) / 2, i, diff);
        modify(2 * n + 1, (s + e) / 2 + 1, e, i, diff);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    int a, b, c;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        if (a == 0) { // 구간 합 쿼리
            if (b < c) {
                cout << sum(1, 0, n - 1, b - 1, c - 1) << '\n';
            } else {
                cout << sum(1, 0, n - 1, c - 1, b - 1) << '\n';
            }
        } else if (a == 1) { // 값 갱신
            int d = c - arr[b - 1];
            arr[b - 1] = c;
            modify(1, 0, n - 1, b - 1, d);
        }
    }
}

---

코드 설명

• 핵심 알고리즘: 세그먼트 트리를 이용해 구간 합을 계산하고, 배열의 특정 값을 변경합니다.
• 구현 세부사항:
  • sum: 특정 구간의 합을 계산하는 함수입니다. 주어진 범위가 세그먼트 트리 노드의 범위와 겹칠 경우 계산합니다.
  • modify: 특정 인덱스의 값을 변경하고, 이에 따른 세그먼트 트리의 변화를 반영합니다.
  • t: 세그먼트 트리 배열로, 구간 합 정보를 저장합니다.
• 시간 복잡도: O(log n) (각 쿼리에 대해)
  • 구간 합 계산: O(log n)
  • 값 갱신: O(log n)

---

결과

주어진 쿼리에 따라 구간 합을 계산하거나, 특정 값 변경 작업을 빠르게 수행합니다. 세그먼트 트리를 활용하여 효율적으로 구현하였습니다.

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