문제 : 모든 원소들이 0으로 초기화된 크기 1,000,000의 수열이 있다. Q개의 쿼리를 처리하자. 쿼리는 2가지 종류가 있다.


1 l r x : 수열의 l~r번째 원소들에 각각 x를 더한다.

2 l r : 수열의 l~r번째 원소들의 합을 구한다.


이 문제는 레이지 세그트리로 Qlogn에 풀 수 있는 유명한 문제이다. 그러나 펜윅 트리 2개를 사용하면 더 빠르고 짧게 해결할 수 있다.


힌트? :

1. 일단 펜윅 트리로 구간 업데이트 점 쿼리를 하는 방법을 알고 있는게 좋다.

2. 각 점의 prefix sum S_i를 ai+b 꼴로 표현한다고 생각하자. 1번 펜윅 트리로 a를 구하고, 2번 펜윅 트리로 b를 구하면 S_i를 빠르게 구할 수 있다.


정답 : https://ideone.com/T0sOTc