Cho một dãy A gồm N phần tử a1, a2,..aN và Q truy vấn, mỗi truy vấn là một trong 2 loại sau:
- Loại 1 có dạng 1 u x: Giá trị phần tử thứ u được thay đổi về x (1 ≤ u ≤ N; |x| ≤ 109);
- Loại 2 có dạng 2 l r: Tính tổng các phần tử từ l đến r (1 ≤ l ≤ r ≤ N).
Yêu cầu: Hãy đưa ra câu trả lời cho mỗi truy vấn loại 2.
Dữ liệu vào: Có cấu trúc như sau:
- Dòng đầu tiên gồm 2 số nguyên N, Q (1 ≤ N, Q ≤ 105);
- Dòng thứ hai chứa N số nguyên a1, a2,..., aN miêu tả giá trị ban đầu của dãy (|ai| ≤ 109);
- Q dòng tiếp theo, mỗi dòng chứa 3 số nguyên miêu tả một trong 2 truy vấn đã được đề cập ở trên.
Kết quả: Ứng với mồi truy vấn loại 2, in ra đáp án tìm được trên một dòng.
Input |
Output |
3 3 1 2 3 1 2 1 2 1 2 2 2 3 |
2 4
|