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

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

문제 접근

• 세그먼트 트리 응용 문제
  • 세그먼트 트리 기본 개념: https://dev-jango.tistory.com/30
  • 수정이 구간으로 이루어질경우 lazy 사용
  • lazy : 해당 노드에 대해서 업데이트 해줘야 할 값
  • 해당 노드를 조회하거나 업데이트처럼 직접 사용할때 한번에 처리
  • 그 전까지는 작업을 뒤로 미뤄둠

시간복잡도 계산

• 처음 세그먼트 트리 생성 : 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 <vector>
#include <cmath>
 
using namespace std;
typedef long long ll;
 
vector<ll> tree;
vector<ll> lazy;
ll 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);
    
    return tree[node] = rsl + rsr;
}
 
// 해당 노드에 있는 lazy를 적용하고 lazy를 비워줌
void lazy_update(int node, int st, int en) {
    if(lazy[node] != 0) {
        tree[node] += (en-st+1) * lazy[node];
        
        if(st != en) {
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        
        lazy[node] = 0;
    }
}
 
void update(int node, int st, int en, int li, int ri, ll diff) {
    // lazy 업데이트 먼저 수행
    lazy_update(node, st, en);
    
    if(ri < st || en < li) return;
    if(li <= st && en <= ri) {
        // 구하려는 구간 안에 노드가 있으면 업데이트 반영
        tree[node] += (en-st+1) * diff;
        if(st != en) {
            lazy[node*2] += diff;
            lazy[node*2+1] += diff;
        }
        return;
    }
    
    int mid = (st+en)/2;
    update(node*2, st, mid, li, ri, diff);
    update(node*2+1, mid+1, en, li, ri, diff);
    tree[node] = tree[node*2] + tree[node*2+1];
}
 
ll sumt(int node, int st, int en, int li, int ri) {
    lazy_update(node, st, en);
    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];
    
    // tree, lazy, 초기화
    int h = ceil(log2(N));
    tree.resize(1<<(h+1));
    lazy.resize(1<<(h+1));
    
    make(1,0,N-1);
    
    for(int i=0; i<M+K; i++) {
        int a,b,c; cin >> a >> b >> c;
        if(a==1) {
            ll d; cin >> d;
            update(1,0,N-1,b-1,c-1,d);
        } else {
            cout << sumt(1,0,N-1,b-1,c-1) << '\n';
        }
        
        
    }
    return 0;
}
 

문제유형

• 세그먼트 트리 - lazy