#6649. 区间求和和区间最小值的结合

区间求和和区间最小值的结合

区间求和和区间最小值的结合**

题目描述: 给定一个整数数组 A,你需要处理 Q 次查询,每次查询可以是:

  1. 区间和查询:查询区间 [L, R] 的元素和。
  2. 区间最小值查询:查询区间 [L, R] 的最小值。

输入:

  • 第一行:一个整数 N,表示数组的大小。
  • 第二行:N 个整数,表示数组的元素。
  • 第三行:一个整数 Q,表示查询的次数。
  • 接下来 Q 行,每行可以是两种类型的操作:
    • 1 L R:区间和查询,表示查询区间 [L, R] 的元素和。
    • 2 L R:区间最小值查询,表示查询区间 [L, R] 的最小值。

输出:

  • 对于每次查询,输出结果。

样例输入:

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

样例输出:

6
2
12

解题思路: 这道题结合了区间和与区间最小值查询,可以通过 前缀和 计算区间和,通过 线段树稀疏表 计算区间最小值。