Thursday, January 1, 2015

POJ 3468 - BIT를 이용해 구간에 값을 더하기

문제 : POJ(PKU) 3468 - A Simple Problem with Integers

열 A[1] A[2] ... A[N]이 주어졌을 때에, 연속된 부분 배열 A[i...j]에 x를 더하는 것과 A[i]+A[i+1]+...+A[j]를 묻는 쿼리 M개가 주어진다.

Binary Indexed Tree 2개를 이용해 O(N log N + M log n)에 해결가능하다.

y[i] = A[i]-A[i-1], z[i] = i*y[i]라고 정의하자.(A[0] = y[0] = z[0] = 0)

A[1]+A[2]+A[3]+A[4]

= y[1]+(y[2]+y[1])+(y[3]+y[2]+y[1])+(y[4]+y[3]+y[2]+y[1])

= 4*y[1] + 3*y[2] + 2*y[3] + y[4]

= 5*(y[1] + y[2] + y[3] + y[4]) - (y[1] + 2*y[2] + 3*y[3] + 4*y[4])

= 5*(y[1] + y[2] + y[3] + y[4]) - (z[1] + z[2] + z[3] + z[4])

일반화해보면

Sum(L, R) = A[L]+A[L+1]+...+A[R-1]+A[R]

= (R-L+1)*(y[L]+y[L+1]+...+y[R-1]+y[R]) - (z[L]+z[L+1]+...z[R-1]+z[R])

구간 A[i...j]에 x를 더하는 것은 i번째와 j+1번째의 y, z값만 변하므로 log N에 갱신 가능.

만약 j가 N이라면 j+1이 존재하지 않는 것에 유의하면 된다.

내 소스코드

No comments:

Post a Comment