2268

집가기 전에 하나 풀고 가겠다고 성급하게 덤볐다가 쓸데없이 두 번 틀린 문제다.

펜윅트리를 다시 정의해서 풀면 된다.

update를 이전 값에서 차이값을 갱신해주면 된다.

#include<cstdio> #define MaxVal 1049577 int tree[MaxVal]; int data[MaxVal]; int read(int idx) { int sum = 0; while(idx > 0){ sum += tree[idx]; idx -= (idx & -idx); } return sum; } void update(int idx, int val) { while(idx <= MaxVal) { tree[idx] += val; idx += (idx & -idx); } } int main(){ int N, M; int a, b, c; scanf("%d %d", &N, &M); for(int clk=0; clk<M; clk++) { scanf("%d %d %d", &a, &b, &c); if(a==0) { if(b<c){ printf("%d\n", read(c)-read(b-1)); } else{ printf("%d\n", read(b)-read(c-1)); } } else { update(b, c-data[b]); data[b] = c; } } return 0; }