统计和(Sum Queries)

题目描述

给定一个长度为 $n(0\leq n\leq 10^5)$，初始值都为 $0$ 的序列，$x(0\leq x\leq 10^5)$ 次的修改某些位置上的数字，每次加上一个数，并在此期间提出 $y(0\leq y\leq 10^5)$ 个问题，求每段区间的和。

输入格式

第一行 $1$ 个整数，表示序列的长度 $n$。

第二行 $1$ 个整数，表示操作的次数 $w(0\leq w\leq 2\times 10^5)$。

后面依次是 $w$ 行，分别表示加入和询问操作。

其中，加入用 x 表示，询问用 y 表示。

$x$ 的格式为 x a b 表示在序列上第 $a$ 个数加上 $b$。保证 $1 \leq a \leq n$，$1 \leq b \leq 10^9$。

$y$ 的格式为 y a b 表示询问 $a$ 到 $b$ 区间的加和。保证 $1 \leq a \leq b \leq n$。

输出格式

每行一个正整数，分别是每次询问的结果。

样例输入 #1

5
4
x 3 8
y 1 3
x 4 9
y 3 4

样例输出 #1

8
17

数据范围

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le w \le 2 \times 10^5$，修改操作满足 $1 \le a \le n, 1 \le b \le 10^9$，询问操作满足 $1 \le a \le b \le n$。

知识点与难度

本题涉及的知识点从属于 CSP-J，难度（CF Rating）：1200。

测试点分布

出处：原题链接