Bảng doanh thu động

Bối cảnh và bài toán

Một chuỗi cửa hàng ghi nhận doanh thu theo ngày. Hệ thống hỗ trợ sửa lại doanh thu của một ngày khi số liệu được đối soát và trả lời tổng doanh thu trên bất kỳ khoảng ngày nào.

Yêu cầu

Xử lý các cập nhật điểm và truy vấn tổng đoạn.

Input

• Dòng 1 chứa n q.
• Dòng 2 chứa n số ban đầu.
• Mỗi truy vấn có dạng 1 k u (gán vị trí k bằng u) hoặc 2 a b (tổng đoạn [a,b]).

Output

In kết quả cho mỗi truy vấn loại 2.

Ràng buộc

• 1 <= n, q <= 2 * 10^5
• 1 <= a[i], u <= 10^9
• 1 <= k <= n
• 1 <= a <= b <= n

Chấm điểm

Ví dụ 1

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. Cập nhật vị trí 3 từ 4 thành 1 làm tổng đoạn 1..4 giảm còn 11.

Ví dụ 2

Input

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

Output

15
10
20

Giải thích. Các truy vấn phản ánh ngay giá trị mới tại vị trí 2.

Thông tin bài tập

Nguồn: Phỏng theo CSES – Dynamic Range Sum Queries.