[백준] No.16975 - 수열과 쿼리 21 (C++, 펜윅 트리)

문제

 

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

16975번: 수열과 쿼리 21

 

 

풀이

 

solved.ac 난이도: Platium 4

 

느리게 갱신되는 세그먼트 트리로 해결할 수 있는 문제이지만 A를 아래와 같이 B에 대하여 나타낸다면 일반적인 세그먼트 트리나 펜윅 트리로도 해결이 가능하다.

동일한 구성의 문제를 느리게 갱신되는 세그먼트 트리로 해결하는 풀이는 아래를 참조하자.

백준 - 구간 합 구하기2(10999)

 

펜윅 트리 모른다면 대해서는 깔끔하게 설명하신 백준님의 게시글을 보고 오자.

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

 

펜윅 트리는 세그먼트 트리와는 다르게 부분 합(첫 원소에서 부터 i개의 값)을 계산하는데 특화되었다.(이 특징이 가장 중요합니다!!!)

백준 님이 설명한 펜윅 트리에서는 점 업데이트(Point Update)와 구간 쿼리(Range query)가 가능하다.

따라서 [L,R]구간의 구간합은 [1,R]까지의 합(pSum(R) ) - [1,L-1]까지의 합( pSum(L-1) )으로 구할 수 있다.

하지만 원소의 업데이트는 한 개씩만 진행할 수 있다.

따라서 이번 문제와 같이 구간의 업데이트를 요구하는 문제는 일일이 원소를 업데이트할 경우 구간 업데이트마다 O(NlogN)의 복잡도가 소요되므로 시간 안에 해결할 수 없다.

 

이번 문제를 해결하기 위해 펜윅 트리의 원소들을 다르게 나타낸다면

구간 업데이트(Range Update)와 점 쿼리(Point query)가 가능한 펜윅트리를 만들 수 있다.

 

문제에서 처리하는 두 가지 질의 아래와 같다.

Query 1:  Ai, Ai+1, ..., Aj에 k를 더한다

Query 2:  Ax 를 출력한다. 

 

길이가 N인 수열 A를 다음과 같이 표현해보자.

 

B[1] =  A[1], B[i] = A[i] - A[i-1]

 

1번 쿼리의 경우: 구간 업데이트(Range Update)

A[i], A[i+1], ... , A[j] 까지에 + k 를 해주어야 한다.

 

이를 B에 대해서 나타내면

B[i] => (A[i] + k) - A[i-1] = B[i] +k

B[i+1] => (A[i+1] + k) - (A[i] + k) = B[i+1]

.

.

.

B[j] => (A[j] + k) - (A[j-1] + k) = B[j]

B[j+1] => A[j+1] - (A[j] + k) = B[j+1] - k

 

즉, B[i]에는 + k, B[j+1]에는 -k만 해주면 구간 업데이트를 구간의 끝점에만 적용해주면 된다.

 

2번 쿼리의 경우 : 점 쿼리(Point query)

A[x]의 값은 B[1] + B[2] +...+ B[x]를 해주면 된다.

A[x] = A[1] + (A[2] - A[1]) + (A[3] - A[2]) + ... + (A[x-1] - A[x-2]) + (A[x] - A[x-1])

(파란 구간의 결국 서로 소거된다.)

 

즉, A를 B로 나타낸 펜윅 트리에서는 A원소의 값을 얻기 위해서 B의 1에서 x까지의 구간 합을 구해주면 된다.

 

그림으로 표현해보자.

일단 배열의 초기 값은 모두 0이다.

 

[3,5]의 구간에 x를 더한다고 하면

B[3] = A[3] - A[2] = x

B[6] = A[6] - A[5] = -x 이므로 각 해당 원소를 update해준다.

 

이 상황에서 A[4]의 값을 구하고 싶다면 

B[4] +  B[3] + B[2] + B[1]의 값을 구하면 된다.

 

B[4](= 0) +  B[3](= 4) + B[2](= 0) + B[1](= 0) = 4

구간의 값 변경에는 원소의 값만 변경하고

오히려 원소 값을 구하기 위해 구간(부분) 합을 이용하는 것을 알 수 있다.

 

비슷한 문제로 아래의 문제도 같은 풀이로 해결 가능하다.

백준 -LRH 식물(2934) + 펜윅 트리-Platium 4

 

본 풀이는 jh05013님의 백준 게시글을 참조하였습니다.

펜윅 트리 200% 활용하기 - Baekjoon Online Judge

 

펜윅 트리에 Lazy propagation을 적용하는 제 게시글의 링크도 남깁니다.

[Fenwick Tree Lazy propagation] - 펜윅 트리에 Lazy propagation 적용하기

코드