Mô tả bài toán: Truy vấn mảng

Bạn được cung cấp một mảng gồm ~n~ số nguyên và cần xử lý ~q~ truy vấn thuộc các dạng sau:

1. Cập nhật giá trị: Cập nhật giá trị tại vị trí ~k~ thành ~u~.
2. Tìm tổng tiền tố lớn nhất: Tìm tổng tiền tố lớn nhất trong đoạn ~[a, b]~.

Input:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~: kích thước mảng và số lượng truy vấn.
• Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, ..., x_n~: các giá trị trong mảng.
• Sau đó có ~q~ dòng, mỗi dòng mô tả một truy vấn:
  • 1 k u: Cập nhật giá trị tại vị trí ~k~ thành ~u~.
  • 2 a b: Tìm tổng tiền tố lớn nhất trong đoạn ~[a, b]~.

Output:

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

Ràng buộc:

• ~1 \leq n, q \leq 2 \cdot 10^5~
• ~-10^9 \leq x_i, u \leq 10^9~
• ~1 \leq k \leq n~
• ~1 \leq a \leq b \leq n~

Ví dụ:

Input:

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

Output:

5
2
0

Giải thích:

1. Ban đầu: [1, 2, -1, 3, 1, -5, 1, 4].
2. Truy vấn 2 2 6: Tổng tiền tố lớn nhất trong ~[2, 6]~ là 5.
3. Cập nhật 1 4 -2: Mảng thành [1, 2, -1, -2, 1, -5, 1, 4].
4. Truy vấn 2 2 6: Tổng tiền tố lớn nhất trong ~[2, 6]~ là 2.
5. Truy vấn 2 3 4: Tổng tiền tố lớn nhất trong ~[3, 4]~ là 0.