1. ST 表（稀疏表）主要用于解决哪种问题？

{{ select(1) }}

• [选项1] 动态区间查询
• [选项2] 静态区间最大值 / 最小值查询
• [选项3] 图的最短路径
• [选项4] 排序优化

---

2. ST 表预处理的时间复杂度是？

{{ select(2) }}

• [选项1] O (n)
• [选项2] O(n log n)
• [选项3] O(n²)
• [选项4] O(log n)

---

3. ST 表查询区间最小值的时间复杂度是？

{{ select(3) }}

• [选项1] O (1)
• [选项2] O(log n)
• [选项3] O(n)
• [选项4] O(√n)

---

4. 定义 ST 表数组st[i][j]时，j通常表示？

{{ select(4) }}

• [选项1] 区间长度为 2^j
• [选项2] 区间左端点
• [选项3] 区间右端点
• [选项4] 查询次数

---

5. 预处理 ST 表时，通常使用哪种递推关系？

{{ select(5) }}

• [选项1] st[i][j] = min(st[i][j-1], st[i+2^(j-1)][j-1])
• [选项2] st[i][j] = min(st[i-1][j], st[i][j-1])
• [选项3] st[i][j] = min(st[i][j+1], st[i+1][j])
• [选项4] st[i][j] = min(st[i-2^(j-1)][j-1], st[i][j-1])

---

6. 以下哪项是 ST 表的局限性？

{{ select(6) }}

• [选项1] 只能处理加法运算
• [选项2] 不支持动态更新
• [选项3] 空间复杂度高
• [选项4] 仅适用于整数数据

---

7. 计算区间长度为len的 ST 表查询时，k值通常取？

{{ select(7) }}

• [选项1] log₂(len)
• [选项2] log₂(len) 向下取整
• [选项3] log₂(len) 向上取整
• [选项4] len / 2

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m;
int a[20][100005];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[0][i]);
	}
	int len = log2(n) + 1;
	for(int i=1;i<=len;i++){
		for(int j=1;j<=n-(1<<i)+1;j++){
			a[i][j]=max(a[i-1][j],a[i-1][j+(1<<(i-1))]);
		}
	}
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		int len = log2(y-x+1);
		printf("%d\n",max(a[len][x],a[len][y-(1<<len)+1]));
	}
	return 0;
}

---

8. 代码中数组a[i][j]的含义是？

{{ select(8) }}

• [选项1] 从位置j开始，长度为2^i的区间最小值
• [选项2] 从位置j开始，长度为2^i的区间最大值
• [选项3] 从位置j开始，长度为i的区间最大值
• [选项4] 从位置j开始，长度为2^i的区间和

---

9. 预处理 ST 表的循环中，n-(1<<i)+1的作用是？

{{ select(9) }}

• [选项1] 防止数组越界
• [选项2] 减少不必要的计算
• [选项3] 优化空间复杂度
• [选项4] 确保区间长度不超过n

---

10. 查询时y-(1<<len)+1计算的是？

{{ select(10) }}

• [选项1] 左端点位置
• [选项2] 右端点位置
• [选项3] 第二个区间的起始位置
• [选项4] 区间长度

---

11. 代码中使用scanf而非cin的主要原因是？

{{ select(11) }}

• [选项1] 代码风格偏好
• [选项2] 减少内存占用
• [选项3] 提高输入效率
• [选项4] 避免类型错误

---

12. 预处理时len = log2(n) + 1的目的是？

{{ select(12) }}

• [选项1] 确定 ST 表的层数
• [选项2] 计算最大区间长度
• [选项3] 优化空间使用
• [选项4] 避免递归过深

---

13. 若输入数据全为负数，代码会？

{{ select(13) }}

• [选项1] 无法正确处理
• [选项2] 返回错误结果
• [选项3] 正常工作
• [选项4] 触发运行时错误

---

14. 代码中1<<i的作用是？

{{ select(14) }}

• [选项1] 计算 2 的 i 次方
• [选项2] 快速乘 2
• [选项3] 位运算优化
• [选项4] 生成掩码