2388 - 数列修改求和2

题目描述

给定一个长度为 n 的数列,数列中默认初始值为 0 ,数列支持 2 种操作:

  1. 修改:将第 a 个数加上值 b

  2. 查询:查询数列中区间为 [a,b] (从第 a 个数开始到第 b 个数结束)的所有数的和。

读入 m 次修改或者查询的指令,针对每次查询,请输出对应的区间和。

输入

输入数据第一行包含两个正整数 n,m (n≤10^5,m≤5 \times 10^5),接下来有 m 行。

每行有三个正整数 k,a,b (k=01a,b≤n),k=0 时表示将 a 处数字加上 bk=1 时表示询问区间 [a,b] 内所有数的和。

输出

对于每个询问输出对应的区间和。(本题读入的 n 个数在 [-2^{31},2^{31}-1] 的范围内,求出的区间和在 [-2^{63},2^{63}-1]

样例

输入

10 20
0 1 10
1 1 4
0 6 6
1 4 10
1 8 9
1 4 9
0 10 2
1 1 8
0 2 10
1 3 9
0 7 8
0 3 10
0 1 1
1 3 8
1 6 9
0 5 5
1 1 8
0 4 2
1 2 8
0 1 1

输出

10
6
0
6
16
6
24
14
50
41
标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 入门


上一题 下一题