【题目描述】
给定一个长度为 N 的整数序列 a0,a1,...,aN−1。依次处理以下 Q 个查询:
0 $p$ $x$:ap←ap+x
1 $l$ $r$:输出 ∑i=lr−1ai
【输入】
第一行包含两个整数 N 和 Q,表示序列长度和查询个数。
第二行包含 N 个整数 a0 a1 ... aN−1,表示初始序列。
接下来 Q 行,每行描述一个查询:
0 p x:ap←ap+x;
1 l r:输出 ∑i=lr−1ai。
输入格式如下:
文本
$N$ $Q$
$a_0$ $a_1$ ... $a_{N - 1}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$
【输出】
对每个 1 l r 查询,输出一行一个整数,表示 ∑i=lr−1ai。
【输入样例】
文本
5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3
【输出样例】
【数据范围】
- 1≤N,Q≤500000
- 0≤ai,x≤1000000000
- 0≤p<N
- 0≤li<ri≤N
【来源】
Library Checker(yosupo06) point_add_range_sum