문제
길이가 n인 배열 A1, A2, ..., An이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.
1 l r c: l ≤ i ≤ r인 모든 i에 대해, Ai에 c를 더한다.
2 l r c: l ≤ i ≤ r인 모든 i에 대해, Ai에 c*(i-l)을 더한다.
3 x: Ax를 출력한다.
이 문제는 Fenwick Tree만을 사용하여 푸는 것을 목표로 한다.
입력
첫째 줄에 배열의 크기 n과 쿼리의 개수 q (1 ≤ n, q ≤ 1,000,000)가 주어진다.
둘째 줄에는 A1, A2, ..., An이 주어진다. (-109 ≤ Ai ≤ 109)
다음 q개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. (1 ≤ l ≤ r ≤ n, -1,000 ≤ c ≤ 1,000)
출력
3번 쿼리가 주어질 때 마다 정답을 한 줄에 하나씩 출력한다.
예제
5 5
1 2 3 4 5
1 2 4 5
3 3
2 1 5 10
3 4
3 5
8
39
45
로그인해야 코드를 작성할 수 있어요.