8/1 연습

2017. 8. 2. 01:23알고리즘 문풀/BOJ 연습

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)\)

'알고리즘 문풀 > BOJ 연습' 카테고리의 다른 글

8/3~8/6 연습  (0) 2017.08.06
8/2 연습  (1) 2017.08.03
7/30 ~ 7/31 연습  (0) 2017.08.01
7/29 연습  (0) 2017.07.30
7/27~7/28 연습  (0) 2017.07.29