[C] 백준 2268 수들의 합 7

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

문제 분석 및 접근 방식

문제에서 요구하는 것은 배열 A에 대해 두 가지 연산을 효율적으로 처리하는 것이다:

1. Sum(i, j): 배열의 A[i]부터 A[j]까지의 합을 구하는 연산.
2. Modify(i, k): 배열의 A[i]를 k로 업데이트하는 연산.

제약 조건에 따르면 배열의 크기(N)와 연산 횟수(M) 모두 최대 1,000,000으로, 최악의 경우 Sum과 Modify 연산을 모두 포함하여 최대 백만 번의 연산을 수행해야 한다. 단순히 모든 구간을 반복하며 합을 구하거나, 각 Modify 연산에 대해 배열을 새로 갱신하면 시간 초과가 발생할 가능성이 높다.

따라서 구간 합과 부분 배열 업데이트를 모두 빠르게 수행할 수 있는 자료 구조가 필요하다. 이때, 세그먼트 트리가 가장 적합한 선택이다.

세그먼트 트리에 대한 설명은 다음의 포스트를 참조하면 된다. 2020.08.08 - [Algorithm] - 세그먼트 트리 (Segment Tree) - C/C++로 설명

세그먼트 트리를 선택한 이유

세그먼트 트리는 구간 합 계산과 개별 요소 업데이트 연산을 효율적으로 처리할 수 있는 자료 구조다. 배열의 구간 합을 O(log N) 시간에 계산할 수 있으며, 특정 위치의 값을 변경하는 것도 O(log N)에 가능하다. 따라서 세그먼트 트리를 사용하면 각 Sum 및 Modify 연산을 빠르게 수행할 수 있다.

세그먼트 트리는 다음과 같은 방식으로 문제 해결에 도움을 준다:

• 구간 합 연산 (Sum): 세그먼트 트리를 통해 구간 합을 O(log N)의 시간에 계산할 수 있다.
• 개별 업데이트 연산 (Modify): 특정 위치의 값을 바꾸면 해당 구간에 포함된 모든 노드들을 O(log N) 시간에 업데이트할 수 있다.

이와 같은 세그먼트 트리의 특징을 활용하면 주어진 제한 내에서 문제를 해결할 수 있다.

---

코드 상세 설명

이제 문제의 요구 사항을 반영하여 세그먼트 트리 구현 코드를 설명한다. 주요 함수는 init (트리 초기화), update (값 변경 시 트리 갱신), sum (구간 합 계산)으로 구성된다.

변수 및 자료 구조 초기화

typedef long long ll;
ll tree[3000000];
ll num[1000001];

• tree: 세그먼트 트리의 각 노드를 저장하는 배열이다. 트리는 최대 4 * N 정도의 크기를 갖도록 한다.
• num: 배열 A의 초기값을 저장하는 배열로, 모든 값을 0으로 초기화한다.

main 함수

int main() {
    int N, M;
    scanf("%d%d", &N, &M);

    memset(tree, 0, sizeof(tree)); // 트리를 0으로 초기화

    for (int i = 0; i < M; ++i) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (a == 1) { // Modify 연산
            int diff = c - num[b];
            num[b] = c;
            update(1, 1, N, b, diff);
        } else { // Sum 연산
            if (b < c)
                printf("%lld\n", sum(b, c, 1, 1, N));
            else
                printf("%lld\n", sum(c, b, 1, 1, N));
        }
    }
}

1. N과 M을 입력받고, 세그먼트 트리를 0으로 초기화한다.
2. 입력된 각 명령을 순차적으로 수행한다.
   • a == 1 (Modify 연산): 배열의 b번째 값을 c로 바꾸고, update 함수를 호출해 트리의 값을 갱신한다.
   • a == 0 (Sum 연산): 구간 [b, c]의 합을 sum 함수로 계산해 출력한다. b와 c의 크기를 비교하여 작은 값에서 큰 값으로 합을 구한다.

update 함수

void update(int n, int s, int e, int t, int diff) {
    if (s <= t && t <= e)
        tree[n] += diff;
    else
        return;

    if (s == e)
        return;

    int m = (s + e) / 2;
    update(n * 2, s, m, t, diff);
    update(n * 2 + 1, m + 1, e, t, diff);
}

• update 함수는 인덱스 t에 해당하는 값이 변경되었을 때 세그먼트 트리에서 해당 구간을 갱신한다.
• tree[n]에 diff 값을 더해 현재 구간의 값을 업데이트하고, 리프 노드에 도달할 때까지 재귀적으로 자식 노드들을 탐색하면서 변경 사항을 반영한다.

sum 함수

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

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

• sum 함수는 구간 [l, r]의 합을 구하는 함수다.
• 노드 구간 [s, e]가 완전히 [l, r]에 포함되면 tree[n] 값을 반환하고, 범위가 겹치지 않으면 0을 반환한다.
• 구간이 부분적으로 겹칠 때는 좌우 자식 노드를 재귀적으로 탐색하여 합산한 결과를 반환한다.

init 함수

ll init(int n, int s, int e) {
    if (s == e)
        return tree[n] = num[s];

    int m = (s + e) / 2;
    tree[n] = init(n * 2, s, m) + init(n * 2 + 1, m + 1, e);
    return tree[n];
}

• init 함수는 세그먼트 트리의 초기 상태를 설정하는 함수다.
• 리프 노드인 경우 tree[n]에 배열의 값을 저장하고, 내부 노드의 경우 좌우 자식의 합을 계산해 저장한다.

---

전체 코드 흐름 요약

1. 입력된 N과 M을 읽고, 세그먼트 트리와 배열을 초기화한다.
2. 각 명령을 순차적으로 수행하며 Modify와 Sum 연산을 처리한다.
   • Modify 연산은 update 함수를 통해 특정 위치의 값을 업데이트하고, 세그먼트 트리에 반영한다.
   • Sum 연산은 sum 함수를 호출하여 구간 합을 계산해 출력한다.
3. 세그먼트 트리의 구조 덕분에, 각 연산을 O(log N) 시간에 처리할 수 있어 대규모 입력에서도 효율적으로 실행된다.