백준 2042 구간 합 구하기 쉬운 풀이(C++/CPP)

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

문제 접근

• 세그먼트 트리 문제 : https://dev-jango.tistory.com/30

시간복잡도 계산

• 처음 세그먼트 트리 생성 : N * lgN
• M+K번 의 수정 및 출력 : (M+K)*lgN
• O((N+M+K) * lgN) = 1e6 * 20 = 2e7

인트 계산

• 세그먼트 트리 값 : 최대값인 2^63이 1e6개 있을경우 제일 상단값은 2^63 * 1e6 = e18 * e6 = e24 >> long long
• 입력으로 들어오는값 모두 최대 2^63 > long long

코드

#include <iostream>
#include <queue>
#include <cmath>
 
using namespace std;
typedef long long ll;
 
vector<ll> tree;
int nums[1000010];
 
ll make(int node, int st, int en) {
    // 시작값과 끝값이 같으면 종료
    if(st == en) return tree[node] = nums[st];
    
    int mid = (st+en)/2;
    ll rsl = make(node*2, st, mid);
    ll rsr = make(node*2+1, mid+1, en);
    // st ~ mid, mid+1 ~ en 의 합으로 리턴
    return tree[node] = rsl + rsr;
}
 
void update(int node, int st, int en, int idx, ll diff) {
    if(idx < st || en < idx) return;
    tree[node] += diff;
    if(st != en) {
        int mid = (st+en)/2;
        update(node*2, st, mid, idx, diff);
        update(node*2+1, mid+1, en, idx, diff);
    }
    return;
}
 
ll sumt(int node, int st, int en, int li, int ri) {
    if (ri < st || en < li) return 0;
    if(li <= st && en <= ri) return tree[node];
    
    int mid = (st+en)/2;
    ll rsl = sumt(node*2, st, mid, li, ri);
    ll rsr = sumt(node*2+1, mid+1, en, li, ri);
    
    return rsl + rsr;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M,K; cin >> N >> M >> K;
    for(int i=0; i<N; i++) cin >> nums[i];
    
    // 세그먼트 크기 초기화
    int h = ceil(log2(N));
    tree.resize(1<<(h+1));
    // 초기 세그먼트 트리 생성
    make(1,0,N-1);
    
    for(int i=0; i<M+K; i++) {
        int a,b; cin >> a >> b;
        ll c; cin >> c;
        if(a==1) {
            ll diff = c - nums[b-1];
            nums[b-1] = c;
            // 구간 업데이트
            update(1,0,N-1,b-1, diff);
        } else {
            // 구간합 구함
            cout << sumt(1,0,N-1,b-1,c-1) << '\n';
        }
    }
    return 0;
}
 

문제유형

• 세그먼트 트리

비슷한 문제

• 세그먼트 lazy : https://www.acmicpc.net/problem/10999