[C++] 2042번 구간 합 구하기 - 자료 구조, 세그먼트 트리

#include <iostream>
#include <vector>

#define FOR(i, k, N) for(int i=k; i<=N; i++)
#define MAX_N 1000001
#define MAX_TR 4000001

using namespace std;
typedef long long ll;

ll N, M, K;  //수의 개수 N, 수의 변경이 일어나는 횟수 M, 구간의 합을 구하는 횟수 K
ll num[MAX_N], tr[MAX_TR];  //수열과 세그먼트 트리

void input()
{
    cin >> N >> M >> K;
    FOR(i, 1, N) cin >> num[i];
}

ll init(ll s, ll e, ll no)
{
    if(s==e) return tr[no]=num[s];
    ll m = (s+e)/2;
    return tr[no] = init(s, m, no*2) + init(m+1, e, no*2+1);
}

ll sum(ll s, ll e, ll no, ll l, ll r)
{
    if(l>e || r<s) return 0;
    if(l<=s && e<=r) return tr[no];
    
    ll m = (s+e)/2;
    return sum(s, m, no*2, l, r) + sum(m+1, e, no*2+1, l, r);
}

void update(ll s, ll e, ll no, ll idx, ll va)
{
    if(idx<s || idx>e) return;
    tr[no]+=va;
    if(s==e) return;
    ll m=(s+e)/2;
    
    update(s, m, no*2, idx, va);
    update(m+1, e, no*2+1, idx, va);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    init(1, N, 1);
    
    FOR(i, 1, M+K) {
        ll a, b, c;
        
        cin >> a >> b >> c;
        
        if(a-1) cout << sum(1, N, 1, b, c) << '\n';
        else {
            update(1, N, 1, b, -num[b]+c);
            num[b]=c;
        }
    }
    
    return 0;
}

세그먼트 트리는 처음배우는 자료구조라서 다른 분들의 블로그를 보면서 공부했다. 세그먼트 트리에 대해서 자세하게 적혀있는 블로그가 있어서 아래에 적어두었다.

 

<참고 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/25643750

로그인

이 코드를 보면 쿼리라는 것을 쓰는 것 같은데 나중에 공부하는 거겠지?

 

 

 

<세그먼트 트리>

https://yabmoons.tistory.com/431

[ 세그먼트 트리(Segment Tree) ] 개념과 구현방법 (C++)

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다