DP与平衡树结合：区间求和问题（USACO金组难度）

题目描述：

给定一个长度为n的数组a，初始时数组中的每个元素都为0。现在有q个操作，每个操作的形式为'1 x'或'2 l r'。

操作1：将a[x]的值加1。

操作2：求出区间[l, r]中每个位置的元素值的和，并输出。

现在，请你编写程序，根据给定的操作序列，输出每个操作2的结果。

输入格式：

第一行包含两个整数n和q，分别表示数组长度和操作数。 接下来q行，每行描述一个操作，格式为'1 x'或'2 l r'。

输出格式：

对于每个操作2，输出一个整数表示该操作的结果。

数据范围：

1 ≤ n, q ≤ 10^5 1 ≤ x ≤ n 1 ≤ l ≤ r ≤ n

示例：

输入： 5 5 1 1 1 2 2 1 2 1 3 2 1 5

输出： 0 1 4