带更新的区间账本

难度：T4

【知识点：区间维护】

前置知识：前缀和、树状数组或线段树、闭区间。

题目描述与输入

首行 $n,q$，第二行 $n$ 个初值。随后 $q$ 行操作。1 p x 表示位置$p$增加$x$；2 l r 查询闭区间和。

输出格式

每个查询单独一行输出区间和。

数据范围

$1\le n,q\le2000$，初值和增量绝对值≤$10^9$；$1\le l\le r\le n$。本题允许 $O(nq)$ 完整通过；要提交复杂度说明，不把本题当作树状数组性能认证。

样例输入

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

样例输出

3
10

样例解释

初始[$2$,$3$]之和$3$，位置$1$增加$5$后全数组之和$10$。