【模板】ST 表 && 区间按位与（AND）问题

📘 题目背景

这是一道 ST 表的经典应用题目，用来练习如何用 ST 表实现静态区间的按位与（AND）查询。

🧾 题目描述

给定一个长度为 \(N\) 的整数数列，和 \(M\) 次区间查询，每次查询给出一个闭区间 \([l_i, r_i]\)，请你输出该区间内所有数的 按位与结果（AND）。

你需要使用 ST 表 数据结构实现每次查询时间为 \(O(1)\) 的算法。

🧩 输入格式

• 第一行包含两个整数 \(N, M\)，分别表示数列的长度与查询的个数。
• 第二行包含 \(N\) 个整数 \(a_1, a_2, ..., a_N\)，表示数列的每一项。
• 接下来 \(M\) 行，每行包含两个整数 \(l_i, r_i\)，表示一次查询的左右端点。

📤 输出格式

• 共 \(M\) 行，每行一个整数，表示对应区间内所有元素的按位与结果。

📌 输入输出样例 #1

输入

8 5
15 7 3 6 12 10 8 9
1 3
2 5
4 6
1 8
3 3

输出

3
0
0
0
3

📊 数据范围与说明

• 对于 \(30%\) 的数据，\(1 \le N, M \le 10\)
• 对于 \(70%\) 的数据，\(1 \le N, M \le 10^5\)

• 对于 \(100%\) 的数据：

  • \(1 \le N \le 10^5\)
  • \(1 \le M \le 2 \times 10^6\)
  • \(0 \le a\_i < 2^{31}\)
  • \(1 \le l\_i \le r\_i \le N\)

🧠 提示

• AND 运算满足幂等律：x & x = x
• ST 表支持对幂等性函数进行高效预处理和查询
• ST 表构建：st[i][j] = st[i][j-1] & st[i + (1 << (j-1))][j-1]
• 查询：将任意长度拆为两个长度 \(2^k\) 区间进行 AND