링크

문제 요약

모든 값이 음이 아닌 정수인 배열이 있다. 이때 구간 $[L,R]$ 에 대하여, $1, 2, \cdots{}, R-L+1$ 만큼이 각 칸에 더해지는 쿼리와, 현재 $X$ 번째 원소의 값을 구하는 쿼리가 주어질 때, 각각에 대하여 답하여라.

관찰

쿼리의 특징을 잘 생각해보자, 어떤 구간에 대하여 $1, 2, \cdots{}, R-L+1$ 을 순서대로 각각 더한 결과물은 자신과 다음원소의 차이 값을 1씩 더한다는 것이다. 따라서 새로운 배열 B를 생각하도록 하자. $B_i=A_i-A_{i-1}$ 이고, 편의상 $A_0=0$ 으로 두자. 이렇게 하면 문제에 주어진 업데이트 쿼리의 경우 구간 $[L,R]$ 에 B 값을 1씩 더한 후, $B_{R+1}$ 에 $R-L+1$ 만큼 빼주는 것으로 해결이 가능하다. 또한 $\displaystyle A_X=\sum_{i=1}^X B_i$ 로 두번째 쿼리를 계산할 수 있다.

풀이

위의 관찰 내용을 이제 빠르게 처리만 하면 문제는 해결된다. 첫번째 쿼리는 특정 구간에 값을 더하는 연산이고, 두번째 쿼리는 구간 합을 구하는 쿼리이다. 이를 빠르게 가능하게 해주는 자료구조는 Lazy propagation을 지원하는 합 세그먼트 트리를 만들면 된다. 해당 자료구조를 이용하면 2개의 쿼리 모두 $O(\log{N})$ 에 해결이 가능하고, 따라서 $O(Q\log{N})$에 문제가 해결된다.