[BOJ 2042 // C++] 구간 합 구하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2042번 문제인 구간 합 구하기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

이 문제는 세그먼트 트리(segment tree) 자료구조를 익히는 기본 문제이다.

세그먼트 트리를 익히기 위해 이 문제를 풀어보았다.

여러 책과 사이트를 참고하여 코드가 부산하지만, 처음으로 세그먼트 트리를 구현해보았다는 데에 의의를 두기로 했다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin; using std::cout;
typedef long long ll;

ll arr[1000001];
ll segtree[4000001];
int N, M, K;

ll seg(int L, int R, int index) { // segment tree 만들기
    if (L == R) segtree[index] = arr[L];
    else segtree[index] = seg(L, (L + R) / 2, index * 2) + seg((L + R) / 2 + 1, R, index * 2 + 1);
    return segtree[index];
}

ll query1(int L, int R, int queryL, int queryR, int index) { // 구간 합 쿼리
    if (queryL <= L && R <= queryR) return segtree[index];
    else if (R < queryL || queryR < L) return 0;
    else  return query1(L, (L + R) / 2, queryL, queryR, index * 2) + query1((L + R) / 2 + 1, R, queryL, queryR, index * 2 + 1);
}

void query2(int L, int R, int qI, int segI, ll diff) { // 값 변경 쿼리
    if (qI < L || R < qI) return;
    segtree[segI] += diff;
    if (L == R) return;
    query2(L, (L + R) / 2, qI, segI * 2, diff);
    query2((L + R) / 2 + 1, R, qI, segI * 2 + 1, diff);
}

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

    cin >> N >> M >> K;
    for (int i = 1;i <= N;i++) {
        ll x; cin >> x; arr[i] = x;
    }
    seg(1, N, 1);
    for (int i = 0;i < M + K;i++) {
        ll a, b, c; cin >> a >> b >> c;
        if (a == 1) {
            query2(1, N, b, 1, c - arr[b]);
            arr[b] = c;
        }
        else cout << query1(1, N, b, c, 1) << '\n';
    }
    return 0;
}