Binary Index Tree를 이용한 풀이를 해야 한다.
주요 알고리즘
void add(int h, int v){ for (int i = h; i <= N; i+=(i&-i)) tree[i]+=v; } long sum(int h){ long r =0; for (int i = h; i > 0 ; i-=(i&-i)){ r+=tree[i]; } return r; } |
미리 합을 구해 놓고, 변경되는 내용에 대해서는 다시 차이값을 저장한다.
static void add(int h, int v, long[] ar) { for (int i = h; i <= MAX_N; i+=(i&-i)) ar[i]+=v; } static long sum(int h, long[] ar) { long result = 0; for (int i = h; i > 0; i-=(i&-i)) result+=ar[i];
return result; } |