RMQ问题,大概是区间多次查询问题。
最近小码君掌握的知识,也可以解决这个简单的RMQ问题了:
给一个数组a,长度为n,每个数组元素a
i
最开始都为0。
接下来有q次询问,其中有两种操作:
· 1 x y z:对数组区间[x,y]的每一个数增加z
· 2 x y:查询数组区间[x,y]中所有元素之和
其中区间[x,y]可以理解成:从x到y中间的所有数,比如x,x+1,x+2,...,y−2,y−1,y
那么数组区间[x,y]即:a[x],a[x+1],...,a[y−1],a[y]
输入格式
第一行包含一个整数n,表示元素个数。
第二行包含一个整数q,表示查询个数。
接下来q行,每行输入一个整数o,表示操作类型。若o=1,则输入三个整数x, y, z;若o=2,则输入两个整数x, y,具体操作如描述所说。
输出格式
对于每个操作2,输出区间[x,y]的区间和,占一行。