U94691.Segment with the Maximum Sum

In this problem, you need to write a segment tree to find the segment with the maximum sum.

第一行包含两个数字 $n$ 和 $m$ （ $1\le n, m\le 100000$ ）。( $1\le n, m\le 100000$ ），即数组的大小和操作次数。下一行包含 $n$ 和 $a_i$ ，即数组的初始状态（ $-10^9\le a_i \le 10^9$ ）。下面几行是操作说明。每个操作的说明如下： $i$ $v$ , 为索引为 $i$ 的元素赋值 $v$ （$0\le i < n$ , $-10^9\le v\le 10^9$ ）。

打印 $m+1$ 行：在所有操作之前和每次操作之后，某段上的最大数字总和。请注意，该数据段可能为空（因此其总和等于 0）。