어느 해양 관측소가 일렬로 늘어선 \(N\) 개의 산호초 구획을 관리한다. 구획은 왼쪽부터 \(1\)번, \(2\)번, \(\dots\), \(N\)번으로 번호가 매겨져 있고, 각 구획에는 지금까지 측정된 생장량이 정수로 기록되어 있다.

관측소는 매일 다음 두 종류의 작업을 수행한다.

• 갱신: 어떤 한 구획의 생장량을 새로 측정한 값으로 교체한다.
• 질의: 연속한 구간에 속한 모든 구획의 생장량 총합을 구한다.

예를 들어 구획 \(5\)개의 초기 생장량이 \(3\ 1\ 4\ 1\ 5\) 라면, 구간 \([2, 4]\) 의 총 생장량은 \(1 + 4 + 1 = 6\) 이다. 여기서 \(3\)번 구획의 생장량을 \(10\) 으로 갱신하면 생장량은 \(3\ 1\ 10\ 1\ 5\) 가 되고, 이제 구간 \([1, 5]\) 의 총 생장량은 \(20\) 이 된다.

처음 생장량과 작업들이 순서대로 주어질 때, 모든 질의에 대해 해당 구간의 총 생장량을 출력하는 프로그램을 작성하라.

\(1 \le N \le 200{,}000\)

\(1 \le M \le 200{,}000\)

모든 생장량 값은 \(0\) 이상 \(10^9\) 이하의 정수이다.

구간 합은 최대 \(200{,}000 \times 10^9 = 2 \times 10^{14}\) 까지 커질 수 있으므로 \(64\)비트 정수를 사용해야 한다.

첫째 줄에 구획의 수 \(N\) 과 작업의 수 \(M\) 이 공백으로 구분되어 주어진다 (\(1 \le N \le 200{,}000\), \(1 \le M \le 200{,}000\)).

둘째 줄에 \(N\) 개의 정수가 주어지며, \(i\)번째 정수는 \(i\)번 구획의 초기 생장량이다 (\(0 \le\) 생장량 \(\le 10^9\)).

다음 \(M\) 개의 줄에는 각각 하나의 작업이 주어진다.

• 1 i v : \(i\)번 구획의 생장량을 \(v\) 로 갱신한다 (\(1 \le i \le N\), \(0 \le v \le 10^9\)).
• 2 l r : 구간 \([l, r]\) 에 속한 구획들의 생장량 총합을 질의한다 (\(1 \le l \le r \le N\)).

각 질의(작업 종류 2)에 대해 한 줄씩, 해당 구간 \([l, r]\) 의 총 생장량을 출력한다.

riseoj 작성

출처 Original