10068 펜윅 트리 Gold I

문제

N개의 수가 주어진다. 다음 두 연산을 처리하는 프로그램을 작성하시오.

1. 1 i v: i번째 수에 v를 더한다.
2. 2 l r: l번째 수부터 r번째 수까지의 합을 출력한다.

입력

첫째 줄에 수의 개수 N (1 ≤ N ≤ 1,000,000), 업데이트 횟수 M (1 ≤ M ≤ 10,000), 쿼리 횟수 K (1 ≤ K ≤ 10,000)가 주어진다. 둘째 줄에 N개의 수가 주어진다. 각 수는 절댓값이 1,000,000 이하이다. 다음 M+K개의 줄에 연산이 주어진다.

출력

구간 합 쿼리에 대해 결과를 한 줄에 하나씩 출력한다.

5 3 3
1 2 3 4 5
2 1 3
1 2 5
2 1 3
1 4 3
2 2 5
2 1 5

6
9
15
18