2042 구간 합 구하기

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

수를 변경하는 쿼리가 없다면 i~j까지의 합을 부분합 S[j]-S[i-1]를 이용하여 O(1)만에 해결할 수 있다. 그러나 수를 변경하는 쿼리가 있기에 위의 방식으로는 수를 변경할 때마다 앞의 모든 부분합을 갱신해줘야 하기에 O(N)이 걸린다. 쿼리수가 M이라고 했을 때 최악의 경우 모든 쿼리가 갱신하는 쿼리라면 O(NM)이 걸리므로 문제를 해결할 수 없다. 세그먼트 트리(Segment Tree)나 펜윅 트리(Fenwick Tree)를 이용하여 업데이트를 O(logN)만에 할 수 있다.

세그먼트 트리 이용

#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
 
ll n,m,k,x,q,b,c,tree[4000000];
 
void update(ll node,ll start,ll end,ll index,ll value)
{
    if(index<start || end<index) return;
    if(start==end) { tree[node]=value; return; }
    update(node*2,start,(start+end)/2,index,value);
    update(node*2+1,(start+end)/2+1,end,index,value);
    tree[node]=tree[node*2]+tree[node*2+1];
}
 
ll query(ll node,ll start,ll end,ll i,ll j)
{
    if(j<start || end<i) return 0;
    if(i<=start && end<=j) return tree[node];
    return query(node*2,start,(start+end)/2,i,j)+query(node*2+1,(start+end)/2+1,end,i,j);
}
 
int main()
{
    scanf("%lld %lld %lld",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%lld",&x),update(1,1,n,i,x);
    for(int i=0;i<m+k;i++)
    {
        scanf("%lld %lld %lld",&q,&b,&c);
        if(q==1) update(1,1,n,b,c);
        else printf("%lld\n",query(1,1,n,b,c));
    }
    return 0;
}

펜윅 트리 이용

#include <cstdio>
typedef long long ll;
 
ll n,m,k,t,a[1000001],tree[1000001];
void update(ll i,ll num) { while(i<=n) tree[i]+=num,i+=i&-i; }
ll sum(ll i) { ll ans=0; while(i>0) ans+=tree[i],i-=i&-i; return ans; }
 
int main()
{
    scanf("%lld %lld %lld",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),update(i,a[i]);
    for(int i=0;i<m+k;i++)
    {
        ll q,b,c,diff;
        scanf("%lld %lld %lld",&q,&b,&c);
        if(q==1) diff=c-a[b],a[b]=c,update(b,diff);
        else printf("%lld\n",sum(c)-sum(b-1));
    }
    return 0;
}