线段树2

题目描述

给$n$个数$a_1, a_2, a_3, \dots, a_n$。

支持$q$个操作：

1. 1 x d，修改$a_x = d$。
2. 2 l r，查询$[l, r]$中的最大子段和，也就是找到$l\leq l'\leq r' \leq r$，使得$\sum_{i=l'}^{r'} a_i$最大。

输入格式

第一行两个整数$n, q (1\leq n, q\leq 2 \times 10^5)$。

接下来一行$n$个整数$a_1, a_2, \dots, a_n (-10^9 \leq a_i\leq 10^9)$。

接下来$q$行，每行一个形如1 x d或者2 l r的操作，保证$1\leq x\leq n, 1\leq l\leq r\leq n, -10^9\leq d\leq 10^9$。

输出格式

对于每个查询，输出一行，表示答案。

样例输入

5 5
-1 2 -3 4 -5
2 4 5
1 2 4
2 1 5
1 4 -1
2 2 4

样例输出

4
5
4