[2042] 구간 합 구하기

// 2042 구간 합 구하기 
// segment tree 
#include <bits/stdc++.h>
#define NMAX 1000000
using namespace std;

int N, M, K;

int a, b;
long long c; // 입력의 수는 -2^63 ~ 2^63-1 

int start;
long long ans;

long long tree[NMAX*3];

// 값 추가 되었을 때 업데이트  
// b번째 수를 c로 바꾼다.  
// 현재 값과 새로운 값의 차이만큼 루트노드로 올라가며 값을 갱신  
void update(int idx, long long value){
	// 값 교체  
	idx = idx + start;
	tree[idx] = value;
	// 그 위의 값들 갱신
	for(int p = idx/2; p > 0; p = p/2){
		tree[p] = tree[p*2] + tree[p*2+1];
	}
}

long long get(int left, int right){
	long long sum = 0;
	// 트리 배열의 인덱스로 변환  
	left = start + left; 
	right = start + right;
	
	while (left <= right){
		if(left % 2 == 1){ // L이 오른쪽에 있으면  
			sum = sum + tree[left]; // sum에 합치고 올라감  
			left ++;
		} 
		if(right % 2 == 0){ // R이 왼쪽에 있으면  
			sum = sum + tree[right]; // sum에 합치고 올라감  
			right --;
		}
		
		// 부모로 올라감  
		left = left / 2;
		right = right / 2;
	}
	return sum;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N >> M >> K;
	int treesize = 1;
	
	while (treesize < N){
		// 노드가 전부 들어갈 트리 사이즈 찾기  
		treesize = treesize * 2;
	}
	memset(tree, 0, treesize * 2 +1);
	start = treesize - 1; // 트리 인덱스를 찾기 위한 값  
	
	// leaf 영역 채우기 
	for(int i=1; i<=N; ++i){
		long long inp;
		cin >> inp;
		tree[start+i] = inp;
	} 
	
	// leaf 제외한 영역 채우기 
	for(int i=start; i!=0; i--){ // 아래 -> 위로 채우기  
		tree[i] = tree[i*2] + tree[i*2+1];
	} 
	
	for(int i=0; i<M+K; ++i){
		cin >> a >> b >> c;
		
		// 업데이트  
		if(a == 1){
			update(b, c);
		}
		// 구간합 구하기  
		else if (a == 2){
			ans = get(b, c);
			cout << ans << "\n";
		}	
	}
	return 0;
}