10999. 구간 합 구하기 2

10999번: 구간 합 구하기 2

---

2042번 구간 합 구하기 1에서는 수가 하나씩 바뀌므로 세그먼트 트리 또는 펜윅 트리를 이용하여 문제를 풀 수 있다.. 그런데 이 문제에서는 $[l,~r]$ 구간의 값이 바뀐다. 따라서 일반적인 세그먼트 or 펜윅 트리를 이용해 값을 갱신하면 한 번의 갱신에 최대 $O(NlogN)$의 시간이 걸리고, 시간 초과를 받을 수밖에 없다.

 

일반적으로 쿼리 문제에서는 쿼리를 로그 시간 안에 해결해야 한다. 그렇다면 구간 갱신을 로그 시간에 수행해야 한다는 뜻인데, 그게 가능할까?

가능하다

세그먼트 트리를 사용한다면 Lazy Propagation이라는 기법을 적용할 수 있다. 느린 전파라는 이름에서도 알 수 있듯이, 값을 매번 갱신하는 게 아니라 값을 새로 계산해야 할 때만 계산하는 알고리즘이다. Lazy Propagation을 적용하면 구간 업데이트를 로그 시간에 수행할 수 있다.

 

나는 펜윅 트리를 사용했는데, 펜윅 트리에서는 다른 알고리즘이 필요하다. 다음 블로그에 깔끔하게 설명돼 있다.

구간 업데이트와 구간 합이 모두 O(logN)에 가능한 펜윅트리 (Fenwick Tree Lazy Propagation)

 

구간 업데이트를 로그 시간에 수행할 수 있어서인지 Lazy Propagation of Fenwick Tree라는 이름으로 불리긴 하지만, 계산 과정은 전혀 다르다. 마치 구간합의 펜윅 트리를 구현하는 느낌.

 

아직 완벽히 이해하진 못했다. 문제를 더 풀어봐야 할 듯.

---