[ BOJ 백준 2042번 - 구간 합 구하기 ] 해설 및 코드

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

 

목적

수의 변경이 빈번하게 일어나는 집합의 부분합을 구하자.

 

접근법

1. 구간합은, O(N)의 시간 복잡도를 가지는 전처리 과정을 거치면, O(1)의 시간 복잡도로 구할 수 있다. 하지만 수정이 일어나면 O(N)의 시간 복잡도로 갱신을 해야한다. 수의 변경이 M번 일어나 O(MN)(=10^10)의 시간 복잡도를 가지므로 TLE가 난다. 이를 해결하기 위해 수정에 걸리는 시간을 O(logN)으로 줄여야 한다. 따라서, 세그먼트 트리를 구현해본다.

 

2. 완전 이진 트리로 구현하여 갱신(update)과 질의(query) 부분 코드를 간단하고 빠르게 하였다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
#define fr(i,l,r) for(int i=l;i>=r;--i)
using namespace std;
typedef long long ll;
 
int n,offset;
ll s[1<<21]{};
 
void update(int i,ll val){
    i+=offset;
    ll add=val-s[i];
    s[i]=val;
    
    while(i>>=1)s[i]+=add;
}
 
ll getSum(int i,int j){
    ll ret=0;
    i+=offset;j+=offset;
    while(i<=j){
        if(i&1)ret+=s[i++];
        if(!(j&1))ret+=s[j--];
        i>>=1;j>>=1;
    }
    return ret;
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int m,k;cin>>n>>m>>k;
    
    offset=1;
    while(offset<n)offset<<=1;
    --offset;
    
    f(i,1,n)cin>>s[i+offset];
    fr(i,offset,1)s[i]=s[i<<1]+s[(i<<1)|1];
    
    m+=k;
    while(m--){
        int a,b,c;cin>>a>>b>>c;
        if(a==1)update(b,c);
        else cout<<getSum(b,c)<<'\n';
    }
    
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.