Fenwick Tree를 이용하기 위해 각 사람의 부하직원들을 구간합을 구할 수 있도록 연속되게 표현해야 한다. 그렇기 때문에 preorder로(dfs가 preorder와 유사한 것을 오늘 깨달았다. 관련 링크 : http://programmers.stackexchange.com/questions/227779/is-pre-order-traversal-same-as-depth-first-search ) 트리를 순회하면 한 노드의 자식들이 연속된 구간으로 나오게 된다. 그래서 Fenwick Tree를 이용할 수 있다.
Baekjoon Online Judge Slack에서 캡쳐.
여기서 preorder로 순회하면서 각 노드의 자식들을 연속된 구간으로 표현하는 것도 어렵지만, 검색해보면 몇몇 블로그에 나와있다. 하지만 Fenwick Tree에서의 range update(구간 갱신)에 대해서는 코드는 있지만 자세한 설명이 없어서 이해하기 힘든 것 같다.
그래서 이것저것 찾아보다가 영어로 된 참조 사이트를 일단 첨부한다. 방법은 다르지만 설명은 좀 잘되어있어서 이해하기는 조금 더 낫다.
TopCoder Forums_FenwickTree_RangeUpdate
https://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/
petr-mitrichev Blog Fenwick Tree Range Updates
petr님의 사이트가 링크 되어있던 sisobus님 블로그
일단 외국사이트 방법대로 풀어보긴 해야겠다. AC는 받았는데, 어제 이해하기 힘들었던 방식을 이해하기 위해서 깔끔하고 이해하기 쉬울 것 같은 Acka님 코드를 계속 봤는데, 도저히 이해가 안되고 이게 과연 정답이 나올까 하는 의문에 결국 내가 직접 test case를 만들어서 실험을 해봤는데, 직접 test를 하면서 내가 여태 이해못했던 이유를 알 수 있었다.
내가 문제를 잘못 이해하고 있었던 것이다... 이 문제는 range update, point query문제였다!! TopCoder Forum에도 댓글에 range update, point query에 대한 설명이 있었는데, 난 무조건 range update, range query로 생각하고 있었기 때문에 전혀 이해 못한 것이었다...
그렇다. 2820문제는 range update, point query문제이기 때문에 Fenwick Tree는 변경하지 않고 간단하게 풀 수 있다. 어찌됐든 이 문제를 풀려면 Fenwick Tree를 응용해야하고, 그에 대한 이해도 충분해야할 것이고... 정말 대단한 것 같다. preorder로 순회해서 자식들을 연속된 구간으로 표현하는 것부터, Fenwick Tree의 응용까지... 멋지다.
약 한달 반 후 다시 봤는데, 내 코드도 이해가 안되고, 링크된 사이트를 봐도 이해가 잘 안된다... 그래서 다시 공부해 보고 여기에 정리해 보려고 한다.
정리할 것은 2가지이다.
1. Fenwick Tree Range Updates and Range Queries
2. Fenwick Tree Range Updates and Point Queries
이 문제를 2가지 방법으로 풀어볼 것이다.
1. Fenwick Tree Range Updates and Range Updates
정말로 range update를 다 해버리면
Topcoder Forum의 AnilKishore님의 설명과 Petr Mitrichev 님의 코드를 보고 생각해보자.
우리는 sum(0 ~ p)값을 구하려 하고, 그 값을 좀 다른 방식으로 표현해보려 한다.
sum(0 ~ p) = mul * p + add <- 이렇게 나타낼 것이다. 그리고 이렇게 나타내기 위해 mul과 add에 해당하는 Fenwick tree를 각각 만들어 놓아야 한다. 즉, Fenwick Tree가 2개 필요하다.
0으로 초기화된 상태에서 범위 a ~ b에 v만큼 더해주는 것은 update(pos, mul, add) 함수를 이용해서 update(a, v, -v*(a-1)), update(b, -v, v*b) 를 해줘야 한다.
이렇게 a번째 위치와 b번째 위치에 해당하는 mul과 add를 업데이트하면 Fenwick tree 그림상에서 a를 끝으로 하는 막대와 그 위의 막대들이 모두 업데이트가 되고, 결국 a이상의 모든 위치에 대해서 query연산을 할 때, a를 업데이트 함으로 인해 업데이트 된 막대기들 중 하나를 이용하게 된다. 즉, a이상의 수들에 대해서 update(a, v, -v*(a-1))이 영향을 끼치게 된다. (단 한 번씩 영향을 끼치기 때문에 여러번 중복되지 않을까 하는 걱정할 필요 없다.)
1. 0 <= p < a 인 경우 mul=0, add=0 -> 아무 영향을 받지 않음. 즉, 0
2. a <= p < b 인 경우 mul=v, add=-v*(a-1) -> v*p - v*(a-1)
3. b <= p <= n 인 경우 mul= v-v = 0, add=v*b - v*(a-1) -> v*b - v*(a-1)
이렇게 모든 위치에 대해서 다 답을 구할 수 있다. 이제 이해는 잘되는데, 어떻게 이런 변형을 생각했는지는 모르겠다. 정말 대단하다.. 아 그리고 위의 예시는 맨 처음에 0으로 초기화 된 상태에서 a ~ b구간을 업데이트 한 것인데, 그 이후에 다른 구간들에 대해 더 업데이트를 해도 잘 생각해보면 적용이 된다.
2. Fenwick Tree Range Updates and Point Queries
point query이기 때문에 정말로 우리가 생각하는 range update를 할 필요가 없다.
일반적인 Fenwick Tree를 그대로 사용하고, 0으로 초기화되어 있는 Fenwick Tree에는 추가되는 값(변경되는 값의 크기)을 저장한다고 할 때,
예를 들어, 구간 [a ~ b]에 v만큼 더 해준다면, [1 ~ a-1]까지는 영향을 받지 않고,
[b+1 ~ n]까지도 영향을 받지 않는다. 그리고 point query이므로 [a ~ b]범위에서 point query를 할 때는 v값이 (b-a+1)번 더해져 있는 값이 아닌, 단 한 번만 더해진 값이면 된다.
그렇기 때문에, [a ~ b]에 v를 더해줄 때는 add(a, v) 와 add(b+1, -v) 만 해주면 된다.
이렇게 하면 [1 ~ a-1]은 영향을 받지 않고, [a ~ b]는 v만 더한 값이 나올 것이고,
[b+1 ~ n]은 v-v=0이 되어 영향을 받지 않을 것이다.
그리고 추가로 계속 변경되는 값이 들어와서 이런 식으로 업데이트를 해도 다 적용이 된다.
펜윅트리의 쿼리는 1~x까지의 부분합을 구하는 것이기 때문에 이런 방식이 좀 이해가 안될 수 있다. 일단 여기서는 쿼리의 의미를 x값의 변화된 값의 크기라고 볼 수 있다.
그리고 내가 이 것들을 이해하면서 알게 된 펜윅트리의 특성이 있다.
바로 어떤 x에 대해서 add(update)를 하면, 펜윅트리의 그림에서 x의 막대 위에 있는 막대들은 다 add(update)가 되고, x보다 큰 값에 대해서 query를 할 때는 그 query는 반드시 x를 update할 때, update된 막대들 중 하나만을(딱 하나만 이용하게 됨, 여러개 아님!) 계산에 이용하게 된다.
그리고 TopCoder Forum에서 VladBelous라는 분이 위의 range updates, point queries에 대해서 좀 더 쉽게 설명해놓은 것이 있다.
이 fenwick tree를 구성하는 배열을 d라고 하고 원래 배열을 a일 때,
d[0] = a[0]
d[1] = a[1]-a[0]
d[2] = a[2]-a[1]... 이런 식으로 인접한 수의 차이로 d배열을 정의하면
a[k] = d[0]+d[1]+...+d[k]가 된다. 즉 d로 이루어진 fenwick tree에서 query를 할 경우, 구해지는 부분합은 우리가 구하고자 하는 a의 값이 되는 것이다.
그리고 d배열의 의미를 생각하면, 구간 x ~ y를 업데이트할 때, add(x, v), add(y+1, -v)를 하는 것이 쉽게 이해가 된다. 구간 x~y에서는 똑같이 v만큼 업데이트 되니까 d값또한 변경이 없다. 변경이 있는 곳은 d[x] = a[x]-a[x-1] 과 d[y+1]=a[y+1]-a[y] 이 부분이다.
확실히 이렇게 이해하면 매우 쉽게 이해할 수 있다. 이렇게 접근하는 것이 좋아보인다.
이것들을 다시 이해하고 정리하는데 일주일은 걸린 것 같고, 정말 이해가 잘 안되고 너무 귀찮은데 다른 걸 하기에는 이걸 먼저 끝내고 싶고... 찝찝해서.. 결국 이것도 일주일만에 끝내고 일주일동안 아무것도 안해버렸다. 평소에 정리를 잘 해놓고, 즐겁게 공부하자.
기본기를 쌓은 후에는 즐겨야 한다. 그러면 성과는 그 뒤에 저절로 따라온다.
출처 : Topcoder Forum과 petr-mitrichev님의 blog
추가 : 나중에 읽어볼 설명 잘 되어있는 사이트
댓글 없음:
댓글 쓰기