구간 합 구하기

중간에 수를 바꾸고 구간 합을 구하는 문제이다.

그냥 세그먼트 트리를 쓰면 바로 풀린다.

#include<stdio.h>
int N, M, K;
long long arr[1000004];
long long sum[3000004];
long long init(int n, int s, int e)
{
    if(s==e) return sum[n] = arr[s];
    int m = (s+e)/2;
    return sum[n] = init(n*2, s, m) + init(n*2+1, m+1, e);
}
long long fin(int n, int s, int e, int fs, int fe)
{
    if(e<fs || s>fe) return 0;
    if(fs<=s && e<=fe) return sum[n];
    int m = (s+e)/2;
    return fin(n*2,s,m,fs,fe) + fin(n*2+1,m+1,e,fs,fe);
}
void update(int n, int s, int e, int ind, long long diff)
{
    if(ind<s || ind>e) return;
    sum[n] += diff;
    if(s!=e)
    {
        int m = (s+e)/2;
        update(n*2,s,m,ind,diff);
        update(n*2+1,m+1,e,ind,diff);
    }
}
int main()
{
    scanf("%d %d %d",&N,&M,&K);
    for(int i=1;i<=N;i++)
    {
        scanf("%lld",&arr[i]);
    }
    init(1,1,N);
    for(int i=1;i<=M+K;i++)
    {
        long long a,b,c;
        scanf("%lld %lld %lld",&a,&b,&c);
        if(a==1)
        {
            update(1,1,N,b,c-arr[b]);
            arr[b]=c;
        }
        else
        {
            long long ans = fin(1,1,N,b,c);
            printf("%lld\n",ans);
        }
    }
}