CSES2166 前缀和查询
#CS2166. 前缀和查询
前缀和查询
题目背景
翻译自 CSES-2166 题。
题目描述
给定一个包含 n 个整数的数组，你需要处理 q 个查询，查询的类型如下：
-
将位置 k 的值更新为 u。
-
查询区间 [a,b][a,b][a,b] 中的最大前缀和。
输入格式
第一行包含两个整数 n 和 q：分别表示数组的元素个数和查询的数量。
第二行包含 n 个整数 x1,x2,…,xnx_1,x_2,…,x_nx1,x2,…,xn：表示数组的初始值。
接下来有 q 行描述查询。每一行包含三个整数，表示以下两种类型之一：
-
1 k u：将数组中第 k 个位置的值更新为 u。
-
2 a b：查询区间 [a,b][a,b][a,b] 内的最大前缀和。
输出格式
对于每个查询类型为 2 的查询，输出该查询的结果，即区间 [a,b][a,b][a,b] 中的最大前缀和。
样例
8 4
1 2 -1 3 1 -5 1 4
2 2 6
1 4 -2
2 2 6
2 3 4
5
2
0
说明/提示
−109≤xi,u≤109-10^9 \leq x_i,u \leq 10^9−109≤xi,u≤109；