2042 부분합

#include <stdio.h>
#include <cmath>
 
using namespace std;
typedef long long ll;
 
ll arr[1000002] = { 0 };
ll tree[2000010] = { 0 };
ll size,ret=0;
 
void update(ll idx, ll data) {
    idx += size-1;
    tree[idx] = data;
    while (idx > 1) {
        idx /= 2;
        tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
    }    
}
 
void sum(ll left, ll right, ll idx, ll nL, ll nR) {
    if (right < nL || nR < left) {        
        return;
    }
    if (left <= nL&&nR <= right) {        
        ret += tree[idx];
        return;
    }        
    ll mid = (nL + nR) / 2;
    sum(left, right, idx * 2, nL, mid);
    sum(left, right, idx * 2 + 1, mid + 1, nR);
}
 
int main() {
    ll n, m, k;
    scanf("%lld %lld %lld", &n, &m, &k);
 
    for (int i = 1; i < 100; i++) {
        if (n < pow(2, i)) {
            size = (int)pow(2, i);    
            break;
        }
    }
 
    for (ll i = 1; i <= n; i++) {
        ll x;
        scanf("%d", &x);
        update(i, x);
    }    
 
    for (ll i = 0; i < m + k;i++) {
        ll a, b, c;
        scanf("%d %d %d", &a, &b, &c);
 
        if (a == 1) {
            update(b, c);            
        }
        else {
            ret = 0;
            sum(b, c,1,1,size);
            printf("%lld\n", ret);
        }
    }
}