[BOJ-2042]구간 합 구하기 1

구간합을 구하는 문제이다. 

특정 인덱스에 저장된 값을 수정을 계속해서 반복하고,

수정된 값들의 합을 구하는 문제이다. 

펜윅트리(Fen wick Tree ; BIT ; Binary Indexed Tree) 로 풀이한 코드.

#include<cstdio>
#include<vector>
using namespace std;
 
void binary(int n){
    vector<int> ret(32,0);
 
    for(int i = 31 ;  i >= 0 ; i--){
        int print = 1;
        print = print & n;
        ret[i] = print;
        n = n >> 1;
    }
    for(int i = 0 ; i < 32 ; i++){
        printf("%d", ret[i]);
    }
    puts("");
    return ;
}
 
class BIT{
public:
    typedef long long dtype;
    int S;
    vector<dtype> T;
    vector<dtype> A;
 
    BIT(int n): S(n), T(n+1), A(n+1, 0) {}
 
    // p is index;
    // v is A[p] = v;
    void update (int p , dtype v){
        int pivot = p;
        while ( p <= S ){
            T[p] -= A[pivot];
            T[p] += v;
#ifdef DEBUG
            printf("%d\n", p);
            printf("%d\n", -p);
            binary(p);
            binary(-p);
            printf("p & -p = %d\n", p&(-p));
#endif
            p += p&(-p);
        }
        A[pivot] = v;
#ifdef DEBUG
        printf("OUT p : %d\n", p);
#endif
    }
 
    // sum from 1 to p index
    dtype sum ( int p ){
        dtype ret = 0;
        while ( p > 0 ){
            ret += T[p];
            p -= p & (-p);
        }
        return ret;
    }    
 
    void array_print(){
        for(int i = 1 ; i <= S ;i++) printf("%lld\n",A[i]);
        for(int i = 1 ; i <= S ;i++) printf("BIT %lld\n",T[i]);
    }
};
 
 
 
int main(){
 
    int n,m,k; scanf("%d%d%d", &n, &m, &k);
    
    BIT bit(n);
 
    for(int p = 1 ; p <= n ; p++){
        long long input; scanf("%lld", &input);
        bit.update(p, input);
    }
    //bit.array_print();
    for(int i = 1 ; i <= m+k ; i++){
        int s, a, b;
        scanf("%d%d%d", &s, &a, &b);
        if(s==1) bit.update(a, b);
        else if(s==2) printf("%lld\n",bit.sum(b) - bit.sum(a-1));
    }
 
    return 0;
}