2042. 구간 합 구하기

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

2042번: 구간 합 구하기

 

 

티어 : 골드1

 

세그먼트 트리를 이용해서 풀었다.

 

#include<stdio.h>

long long int arr[1000005], seg[4000005];
int n, m, k;

long long int init(int index, int left, int right){
    if(left == right) return seg[index] = arr[left];
    int mid = (left + right) / 2;
    return seg[index] = init(index*2, left, mid) + init(index*2+1, mid+1, right);
}

void update(int index, int left, int right, long long int value, int findIndex){
    if(left <= findIndex && findIndex <= right){
        seg[index] += value;

        if(left == right) return ;
        int mid = (left + right) / 2;
        update(index*2, left, mid, value, findIndex);
        update(index*2+1, mid+1, right, value, findIndex);
    }
}

long long int sum(int index, int left, int right, int start, int end){
    if(start <= left && right <= end) return seg[index];
    if(start > right || end < left) return 0;
    int mid = (left + right) / 2;
    return sum(index*2, left, mid, start, end) + sum(index*2+1, mid+1, right, start, end);
}

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=0 ; i<m+k ; i++){
        long long int a, b ,c;
        scanf("%lld %lld %lld", &a, &b, &c);

        if(a == 1){
            update(1, 1, n, c-arr[b], b);
            arr[b] = c;
        }
        else{
            printf("%lld\n", sum(1, 1, n, b, c));
        }
    }
}