구간 합 구하기( BOJ 2042 )

(1) 문제

2042. 구간 합 구하기 : www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

(2) 문제 이해하기

 

(3) 문제 해결하기

 

(4) 소스코드

#include <stdio.h>
#include <vector>
#define NMAX 1000010
using namespace std;
 
// 입력 변수
int n, m, k;
long long int t, a, b, c;
long long int inp[NMAX];
 
// BIT 변수
long long int BIT[NMAX];
 
// 결과 변수
vector< long long int > ans;
 
 
void update(int idx, long long int val) {
    long long int diff = val-inp[idx];
 
    for(int i=idx;i<=n;i+=(i&-i)) BIT[i] += diff;
    inp[idx] = val;
 
}
 
long long int search(int idx) {
    long long int ret=0;
 
    for(int i=idx;i>0;i-=(i&-i)) ret += BIT[i];
 
    return ret;
}
 
int main() {
    // input
    scanf("%d %d %d", &n, &m, &k);
    for(int i=1;i<=n;i++) {
        scanf("%lld", &t);
 
        // make BIT
        update(i, t);
    }
 
 
 
    // query
    for(int i=1;i<=m+k;i++) {
        scanf("%lld %lld %lld", &a, &b, &c);
 
        if(a==1) update(b, c);
        else ans.push_back(search(c) - search(b-1));
    }
 
    // print
    for(long long int val:ans) printf("%lld\n", val);
 
}

 

(5) 후기

세그먼트 트리 혹은 펜윅트리(BIT)를 연습할 수 있는 기본적인 문제입니다. 세그먼트 트리를 배운 다음 펜윅트리를 배울 때, 다시 풀어보기 좋은 문제인듯 합니다.