8/1 연습

2820. 자동차 공장

문제 : http://icpc.me/2820

세그먼트 트리의 클래식한 활용 문제. 사실 suhgyuho가 준 문제집에 있던 건데 이제서야 풀었다(...)

이 문제의 아이디어는 트리를 Segment Tree나 Fenwick Tree같은 구간 자료구조와 엮을 때 자주 쓰는 트릭 중 하나인데, 어떤 노드 \(v\)의 서브트리 (\(v\) 포함) 를 DFS-numbering에서 붙은 번호 \([d[v], f[v]]\)의 구간으로 처리하는 것이다. 

이 트릭을 적용하고 나면 문제의 쿼리는 이렇게 바뀐다 : 

p 쿼리 : 구간 \((d[a],f[a])\)의 원소에 \(x\)를 더한다. (range update)

u 쿼리 : 구간의 \(d[a]\)번째 원소의 값을 구한다. (point query)

range update는 lazy propagation으로 가능한데, imeimi2000은 그렇게 안하나보다... Fenwick Tree에서도 Range update를 처리할 수 있다고 한다. 해봐야지...

https://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/

Time Complexity : \(O(N + M lg N)\)