indexTree.cpp

#include <iostream>
#include <cstdio>
 
using namespace std;
 
#define MAXN 1000100
 
int p = 1;
int N, M, K, a, b, c;
long long indexTree[4 * MAXN];
long long arr[MAXN];
 
void init(void){
    while (N > p) p <<= 1;
    //바닥층 초기화
    for (int i = 0; i < N; i++)
        indexTree[p + i] = arr[i];
    //부모 초기화
    for (int i = p - 1; i >= 1; i--)
        indexTree[i] = indexTree[i * 2] + indexTree[i * 2 + 1];
}
 
//원래 배열 인덱스 index에 value를 더해준다.
void update(int index, int value){
    index += p;
    indexTree[index] = value;
    for (int i = (index >> 1); i >= 1; i >>= 1)
        indexTree[i] = indexTree[i * 2] + indexTree[i * 2 + 1];
}
 
//원래 배열 인덱스 left부터 right까지의 합을 구한다.
long long find(int left, int right){
    left += p;
    right += p;
    long long result = 0;
 
    while (left <= right){
        if (left & 1){
            result += indexTree[left];
            left++;
        }
        if (!(right & 1)){
            result += indexTree[right];
            right--;
        }
        left >>= 1, right >>= 1;
    }
 
    return result;
}
 
int main(){
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);
    init();
    for (int i = 1; i <= M + K; i++){
        scanf("%d%d%d", &a, &b, &c);
        if (a == 1)
            update(b - 1, c);
        else
            printf("%lld\n", find(b-1, c-1));
    }
 
    return 0;
}