[BOJ] #2268 수들의 합 7

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

---

세그먼트 트리의 가장 대표격이라 할 수 있는 구간합 구하기 문제이다.

하지만 이 문제에서 유의해야 할 부분이 두가지가 있는데,

1. (i > j일 경우에는 A[j] + A[j+1] + ... + A[i]) A가 주어졌을 때, Sum(i, j)를 구하는 것은 매우 쉬운 문제이다. 라고 나와있듯, 이 문제에서는 i > j 인 경우 말고도 i < j 인 경우 또한 생각해서 풀어야 한다. 필자도 이 부분을 간과하여 여러번 틀렸다... 그냥 입력받을때, right보다 left가 클때 swap을 이용해서 서로 바꿔주면 해결할 수 있다.

2. 최대가 1,000,000인 경우까지 다루다 보니, 자료형을 신경써야한다. 물론 이는 세그먼트 트리 문제를 풀다보면 어지간해선 다 long long형을 쓰기 마련이지만, 필자는 그냥 아무생각 없이 int로 처음에 풀었다가 틀렸다...

이 두 부분만 주의해서 풀면 나머지는 세그먼트 트리를 이용해 부분합을 구하는 다른 문제들과 별 다른것이 없다.

#include <iostream>

#define MAX 1000001
#define TREE_HEIGHT MAX*4

using namespace std;

int N,M;

int arr[MAX];
long long segTree[TREE_HEIGHT];

long long init(int start, int end, int node) {
    if (start == end) 
        return segTree[node] = arr[start];

    int mid = (start + end) / 2;

    long long tmp_left = init(start, mid, node*2);
    long long tmp_right = init(mid+1, end, node*2+1);
    return segTree[node] = tmp_left + tmp_right;
}

long long subSum(int start, int end, int node, int left, int right) {
    if (left > end || right < start) 
        return 0;

    if (left <= start && right >= end) 
        return segTree[node];

    int mid = (start + end) / 2;

    long long tmp_left = subSum(start, mid, node*2, left, right);
    long long tmp_right = subSum(mid+1, end, node*2 + 1, left, right);
    return tmp_left + tmp_right;
}

void update(int start, int end, int node, int targetIdx, long long val) {
    if (targetIdx > end || targetIdx < start)
        return ;

    segTree[node] += val;

    if (start == end)
        return ;

    int mid = (start + end) / 2;

    update(start, mid, node*2, targetIdx, val);
    update(mid+1, end, node*2+1, targetIdx, val);
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> M;

    for (int i=0; i<N; i++) {
        arr[i] = 0;
    }

    init(0, N-1, 1);

    while (M-->0) {
        int mode, a, b;

        cin >> mode >> a >> b;

        switch(mode) {
            case 0: {
                a--; b--;

                if (a > b) {
                    swap(a,b);
                }

                int total = subSum(0, N-1, 1, a, b);
                cout << total << '\n';

                break;
            }
            case 1: {
                a--;

                long long tmp = b - arr[a];
                arr[a] = b;
                update(0, N-1, 1, a, tmp);

                break;
            }
        }
    }

    return 0;
}

......