펜윅 트리의 응용 - 구간 업데이트, 점 쿼리

펜윅 트리를 모른다면 다음 글을 참고하자.

펜윅 트리 (바이너리 인덱스 트리)

기본적인 펜윅 트리는 점 업데이트, 구간 쿼리를 각각 로그 시간에 수행할 수 있다. 하나의 수를 로그 시간에 업데이트하고, 구간의 합을 로그 시간에 구할 수 있다는 뜻이다.

 

반대로 구간 업데이트와 점 쿼리도 각각 로그 시간에 수행할 수 있다.

어떻게요?

수열 $A$에 대해 구간 업데이트와 점 쿼리를 수행해야 한다고 가정하자.

 

수열 $B$를 $B[1] = A[1],~B[i]=A[i]-A[i-1]~(i \ge 2)$로 정의하고, $B$의 펜윅 트리를 만든다. 이제 구간 업데이트와 점 쿼리를 수행해 보자.

구간 업데이트

$A$의 $[l,~r]$ 구간에 $k$를 더하는 구간 업데이트가 주어진다. 이때 $B$의 변화를 보면 다음과 같다.

 

$B[l] = (A[l]+k) - A[l-1]$

$B[l+1] = (A[l+1]+k) - (A[l]+k)$

$\cdots$

$B[r]=(A[r]+k)-(A[r-1]+k)$

$B[r+1] = A[r+1]-(A[r]+k)$

 

값을 잘 보면 $B[l]$은 $k$ 증가하고, $B[l+1]$부터 $B[r]$까지는 값이 변하지 않고, $B[r+1]$은 $k$ 감소한다. 따라서  $A$의 $[l,~r]$ 구간에 $k$를 더하는 구간 쿼리를 $B[l]$을 $k$ 증가시키고, $B[r+1]$을 $k$ 감소시키는 점 쿼리로 바꿀 수 있다.

점 쿼리

이제 $A$의 $x$번째 값을 구해야 한다. $B$의 정의에 의해 다음이 성립한다.

 

$\sum_{i=1}^{x}{B[i]}=A[1]+(A[2]-A[1])+(A[3]-A[2])+\cdots+(A[x]-A[x-1])=A[x]$

 

따라서 $A$의 점 쿼리를 $B$의 구간 합 쿼리로 바꿀 수 있다. $A[x]$를 구하고 싶다면 $B[1]$부터 $B[x]$까지의 합을 구하면 된다.

 

아이디어는 어렵지만, 알기만 하면 요긴하게 써먹을 수 있을 듯.

---

예제 문제로 16975번 문제를 풀어 보자. 위에서 말한 알고리즘을 구현하기만 하면 된다.

16975번: 수열과 쿼리 21

---

그와중에 컴파일 에러 내는 당신은 도대체