Truy vấn tổng đoạn động (Dynamic Range Sum Queries)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một mảng gồm $n$ số nguyên. Có $q$ thao tác. Mỗi thao tác hoặc gán một giá trị mới cho một vị trí, hoặc yêu cầu tính tổng các phần tử trên một đoạn liên tiếp của mảng.

Input

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Dòng thứ hai chứa $n$ số nguyên $x_1,x_2,\ldots,x_n$.
• Mỗi trong $q$ dòng tiếp theo có dạng 1 k u để gán $x_k=u$, hoặc 2 a b để hỏi tổng $x_a+x_{a+1}+\cdots+x_b$.

Output

Với mỗi thao tác loại 2, in tổng của đoạn được yêu cầu trên một dòng.

Subtask

• Subtask 1 — 20%: $1 \le n,q \le 1000$, $1 \le x_i,u \le 10^6$.
• Subtask 2 — 30%: $1 \le n,q \le 50000$, $1 \le x_i,u \le 10^9$.
• Subtask 3 — 50%: $1 \le n,q \le 2\cdot10^5$, $1 \le x_i,u \le 10^9$.

Ví dụ

Input

8 4
3 2 4 5 1 1 5 3
2 1 4
2 5 6
1 3 1
2 1 4

Output

14
2
11

Giải thích

Ban đầu, tổng đoạn $[1,4]$ là $3+2+4+5=14$ và tổng đoạn $[5,6]$ là $1+1=2$. Sau thao tác 1 3 1, phần tử thứ ba đổi từ $4$ thành $1$, nên tổng mới của đoạn $[1,4]$ là $3+2+1+5=11$.