https://www.acmicpc.net/problem/2042

해결법

인덱스 트리를 구현하면 되는 문제이다.
문제 이곳저곳에서 다양하게 쓰일 수 있다고 하니 외워두도록 하자!
크기가 2N인 배열에 bottom-up 방식으로 구현했다.

인덱스 트리의 사용

배열의 정보가 계속 변하면서
구간의 합 / 구간의 Min or Max / 구간의 곱 등 구간의 정보를 구해야 할 때

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll MAX = 2e6;

ll N,M,K;
ll power2;
ll t[2*MAX+1];

//인덱스 트리를 구성
void init(){
  for(ll i = power2-1; i>0; i--){
    t[i] = t[i<<1] + t[i<<1|1];
    //t[i] = t[i*2] + t[i*2+1]
  }
}

//데이터 갱신
void update(ll position, ll value){
  position = position + power2 - 1;
  t[position] = value; //리프노드 데이터 업데이트
  for(; position>1; position>>=1){
    t[position >> 1] = t[position] + t[position ^ 1];
  }
}

//쿼리 수행
ll query(ll l, ll r){
  ll ret = 0;
  l = l + power2 - 1;
  r = r + power2 - 1;
  for (; l <= r; l >>= 1, r >>= 1) {
    if (l & 1) ret += t[l++]; 
    if (!(r & 1)) ret += t[r--];
  }
  return ret;
}

int main() {

  cin>>N>>M>>K;
  for(power2=1; power2<N; power2<<=1);
  //리프노드 입력
  for(ll i = 0; i<N; i++){
    scanf("%lld",&t[power2+i]);
  }

  init();
  
  for(ll i = 0; i<M+K; i++){
    ll a,b,c;
    cin>>a>>b>>c;
    if(a == 1){ //update
      update(b,c);
    }
    else{ // query
      cout<<query(b,c)<<"\n";
    }
  }
}

제출결과

다채로운 제출결과 ^^!!
2년전의 애송이 나 그리고.. 런타임 에러 나고 급하게 고쳐보려다 컴파일에러를 내버린 나^^,,,,,
배열을 아주 크게 잡아주고.. 해결