位运算基础

1. 万物皆数，从二进制谈起

在深入任何技巧之前，我们必须回到原点。计算机科学的宏伟大厦，建立在坚实的二进制地基之上。

1.1 为何是二进制？

我们生活在十进制的世界，因为我们有十根手指。而计算机的世界，建立在晶体管之上。晶体管最稳定、最易于区分的状态只有两种：导通（高电平）和截止（低电平）。这两种状态，天然地对应了数学中的两个符号：1和0。这种选择并非偶然，而是物理现实与信息表达之间最经济、最可靠的折中。因此，理解二进制，就是理解计算机的“母语”。

1.2 整数的二进制表示

一个非负整数 在二进制下的表示，是将其唯一地分解为2的幂之和的形式：

其中系数 。这个二进制表示写作 。

例如，十进制数 ：

所以， 的二进制表示是 1101。在C++中，一个32位的 int 类型的 13，其内存中的表示实际上是 00000000 00000000 00000000 00001101。最右边是最低位（Least Significant Bit, LSB），最左边是最高位（Most Significant Bit, MSB）。

1.3 负数的表示法：补码的奥秘

这是许多选手会忽略，但却至关重要的一个知识点。计算机如何表示负数？原码、反码、补码是三种历史中出现过的方案，而现代计算机毫无例外地采用补码（Two’s Complement）表示法。

定义：

• 正数：补码与原码相同。
• 负数：其补码为将其绝对值的二进制表示按位取反，再加1。

一个更本质的定义：对于一个 位的有符号整数，其补码表示的数值范围是 。一个二进制串 $(b_{w-1}b_{w-2}\dots b_0)2$ V = -b{w-1} \cdot 2^{w-1} + \sum_{i=0}^{w-2} b_i \cdot 2^i $$
注意最高位 的权重是负的。

示例（以8位整数为例）：

• 7 的二进制是 00000111。
• -7 的补码：
  1. 7 的二进制：00000111
  2. 按位取反（~）：11111000
  3. 加一：11111001
     所以 -7 在8位系统中的表示是 11111001。

为何使用补码？
核心优势在于，补码使得加法和减法运算可以统一处理。计算 等价于计算 ，而硬件只需要实现一个加法器即可，无需为减法设计专门的逻辑。

例如，计算 ：

• 是 00001010
• 是 11111001
• 相加（忽略溢出到第9位）：00001010 + 11111001 = (1)00000011
• 结果是 00000011，即十进制的 。完美！

特别地，-1 的补码是什么？对 1 (00...01) 取反得 11...10，再加一得 11...11。所以一个所有位都为1的二进制数，在有符号整数中代表-1。

这个性质是 lowbit 等技巧的理论基础，我们稍后会看到。

2. 基本位运算符

C++提供了六种位运算符，它们是你进行微观操作的利器。让我们逐一解剖。

2.1 按位与 (AND): &

• 规则：逐位比较，两位都为1时，结果位才为1，否则为0。

• 真值表：
  
  
  
  

• 示例：
  13 & 27
13 = (00001101)_2
27 = (00011011)_2
  ``
  & (00001001)_2 = 9

• 核心用途：

  1. 掩码（Masking）：提取一个数的特定位。例如，要判断 n 的第 k 位是否为1，可以使用 n & (1 << k)。如果结果不为0，则该位为1。
  2. 清零（Clearing）：将某些位清零。例如，要将 n 的后4位清零，可以 n & (~0b1111)。

2.2 按位或 (OR): |

• 规则：逐位比较，两位中只要有一位为1，结果位就为1。

• 真值表：
  
  
  
  

• 示例：
  13 | 27
13 = (00001101)_2
27 = (00011011)_2
  ``
  | (00011111)_2 = 31

• 核心用途：

  1. 置位（Setting）：将某些位置为1。例如，要将 n 的第 k 位置为1，可以使用 n | (1 << k)。
  2. 合并状态：在状态压缩中，将多个状态标志合并到一个整数中。

2.3 按位异或 (XOR): ^

• 规则：逐位比较，两位相异时（一个0一个1），结果位为1，否则为0。可以理解为“无进位的加法”。

• 真值表：
  
  
  
  

• 示例：
  13 ^ 27
13 = (00001101)_2
27 = (00011011)_2
  ``
  ^ (00010110)_2 = 22

• 核心性质与用途：

  1. 自反性：。一个数与自身异或，结果为0。
  2. 幺元：。任何数与0异或，结果是其本身。
  3. 交换律与结合律：, 。这使得一串数字的异或和与顺序无关。
  4. 翻转（Toggling）：将 n 的第 k 位翻转（0变1，1变0），可以使用 n ^ (1 << k)。
  5. 寻找单独出现的数：在一堆数中，除了一个数出现一次外，其他都出现两次，将所有数异或起来，结果就是那个单独的数。
  6. 不使用临时变量交换两数（面试题经典，实战少用）：a^=b; b^=a; a^=b;。请自行推导其正确性。

2.4 按位非 (NOT): ~

• 规则：单目运算符，将一个数的所有二进制位翻转（0变1，1变0）。
• 示例：
  假设为8位整数，~13
13 = (00001101)_2
  ``
  ~ (11110010)_2
• 重要提醒：~n 的值不等于 n 的相反数！根据补码，~n = -n - 1。例如，~13 = -14。这是一个需要牢记的恒等式。

2.5 左移 (Left Shift): <<

• 规则：a << b 将 a 的所有二进制位向左移动 b 位，右边空出的位用0填充。
• 效果：在不发生溢出的情况下，a << b 等价于 。
• 示例：
  13 << 2
13 = (...00001101)_2
<< 2
(...00110100)_2 = 52
13 * 2^2 = 13 * 4 = 52。

2.6 右移 (Right Shift): >>

• 规则：a >> b 将 a 的所有二进制位向右移动 b 位。
• 效果：a >> b 等价于 。
• 重要陷阱：算术右移 vs. 逻辑右移
  • 逻辑右移 (Logical Right Shift)：左边空出的位用0填充。这适用于无符号整数（unsigned int）。
  • 算术右移 (Arithmetic Right Shift)：左边空出的位用符号位填充。如果原数是正数（符号位为0），则填充0；如果是负数（符号位为1），则填充1。这适用于有符号整数（int, long long）。C++标准并未强制规定有符号数必须是算术右移，但几乎所有现代编译器和平台都如此实现。
• 示例：
  • 正数：13 >> 2
13 = (00001101)_2
>> 2
(00000011)_2 = 3
floor(13 / 4) = 3。
  • 负数（8位，补码）：-13 >> 2
-13 = (11110011)_2
>> 2 (算术右移)
    (11111100)_2 = -4
floor(-13 / 4) = -4。

提醒：在竞赛中，当你处理的数字可能为负时，对右移操作要格外小心。如果你想确保是逻辑右移，请将变量强制转换为无符号类型，如 (unsigned)n >> k。通常，我们用位运算处理的都是非负整数（如状态、掩码），这时可以放心使用。

3. 位运算常用技巧 (Common Idioms)

掌握了基本运算符，就像学会了字母。现在，我们要用这些字母来组成常用词汇。这些“惯用法”是你在赛场上快速、准确解题的关键。

3.1 获取与设置特定位

这是最基础的操作，也是所有位运算应用的起点。假设我们关心整数 n 的从右往左数的第 k 位（从0开始计数）。

• 获取第 k 位的值（0或1）

  int get(int n, int k) {
      return (n >> k) & 1;
  }

  解释：n >> k 将第 k 位移动到最低位（第0位），然后 & 1 屏蔽掉所有其他高位，只留下最低位的值。

• 将第 k 位置为 1 (Set)

  int set(int n, int k) {
      return n | (1 << k);
  }

  解释：1 << k 会创建一个只有第 k 位是1的数（例如 k=3 时是 ...001000）。与 n 进行或运算，n 的第 k 位因为 | 1 必然变成1，其他位因 | 0 保持不变。

• 将第 k 位清零 (Clear)

  int clr(int n, int k) {
      return n & (~(1 << k));
  }

  解释：1 << k 得到第 k 位为1的数。~ 取反后，得到一个只有第 k 位是0，其他位全是1的掩码。与 n 进行与运算，n 的第 k 位因为 & 0 必然变成0，其他位因 & 1 保持不变。

• 将第 k 位翻转 (Toggle)

  int tgl(int n, int k) {
      return n ^ (1 << k);
  }

  解释：利用异或的性质。n 的第 k 位与1异或，1^1=0, 0^1=1，实现了翻转。其他位与0异或，保持不变。

3.2 lowbit：树状数组的基石

lowbit(n) 是一个非常重要的操作，它返回 n 的二进制表示中，最低位的1和它后面的0所组成的数值。

• 定义：lowbit(n) = n & -n

• 示例：
  n = 12 = (1100)_2
-n (补码): ~n + 1 = (0011)_2 + 1 = (0100)_2 = 4
n & -n = (1100)_2 & (0100)_2 = (0100)_2 = 4
lowbit(12) 的结果是 4。

• 原理推导：
  我们知道 -n 的补码表示是 ~n + 1。
  假设 n 的二进制表示为 (...10...0)_2，最低位的1在第 k 位，即后面有 k 个0。

  • n = ...b_{k+1}10...0
  • ~n 就是 ...~b_{k+1}01...1 (1变0，0变1)。
  • ~n + 1，由于末尾是一串1，加1会发生连续进位，直到遇到第一个0。于是 ...~b_{k+1}01...1 + 1 = ...~b_{k+1}10...0。
    现在我们来计算 n & (~n + 1):
    (...b_{k+1}10...0) & (...~b_{k+1}10...0)
  • 高于第 k 位的部分，是 b_{k+1} & ~b_{k+1}，结果必为0。
  • 第 k 位，是 1 & 1，结果为1。
  • 低于第 k 位的都是0，结果也为0。
    最终结果为 (...0010...0)_2，这正是第 k 位那个1所代表的数值。

• 核心应用：
  lowbit 是树状数组（Fenwick Tree）的核心。树状数组通过 i += lowbit(i) 在树中向上移动，通过 i -= lowbit(i) 分解区间，其精妙的结构完全建立在 lowbit 的代数性质之上。

3.3 判断是否为2的幂

• 方法：n > 0 && (n & (n - 1)) == 0

• 原理：
  一个正整数 n 是2的幂，当且仅当它的二进制表示中有且仅有一个1 (例如 8 = (1000)_2)。

  • 如果 n = (..10..0)_2，即第 k 位是1，后面全是0。
  • 那么 n - 1 就是 (..01..1)_2，即第 k 位变为0，后面的0全变为1。
  • n & (n - 1) 会将这两部分按位与，(..10..0)_2 & (..01..1)_2 = 0。
    如果 n 不是2的幂，那么它至少有两个1。n - 1 的操作只会影响到最低位的1及其后面的位，更高位的1不受影响，所以 n & (n - 1) 的结果不会是0。
    n > 0 的判断是为了排除 n=0 的情况，因为 0 & -1 也等于0。

3.4 统计二进制中1的个数 (Population Count)

统计一个整数二进制表示中1的个数，也称作计算“汉明权重”。

• 方法一：GCC/Clang 内建函数 (推荐)
  C++的GCC和Clang编译器提供内建函数，它们会被编译成单条CPU指令（如 POPCNT），效率极高。

  int n;
  cin >> n;
  cout << __builtin_popcount(n); // for int
  
  long long m;
  cin >> m;
  cout << __builtin_popcountll(m); // for long long

  在竞赛中，请大胆使用。这是最快、最简洁的方法。

• 方法二：Brian Kernighan 算法
  如果环境不支持内建函数，或者你想理解其原理，这个算法非常优雅。

  int cnt = 0;
  while (n > 0) {
      n &= (n - 1);
      cnt++;
  }

  原理：n & (n - 1) 这个操作，我们刚才见过。它的效果是将 n 的二进制表示中最低位的那个1变成0。
  因此，循环的次数就等于 n 中1的个数。
  复杂度：，其中 是 n 中1的个数。在最坏情况下（n 的所有位都是1），复杂度等于位数。

4. 实战演练：从思维到代码

理论和技巧的价值在于应用。让我们通过几个经典的例子，看看如何将位运算思维融入算法设计中。

4.1 快速幂：二进制拆分的威力

题意概括:
给定三个整数 ，求 的值。

分析:
最朴素的想法是循环 次，每次乘以 再取模，时间复杂度为 。当 很大时（例如 ），这种方法会超时。

核心思想：二进制拆分
任何一个指数 都可以进行二进制拆分。例如 ，其二进制是 1101。

于是：

这个观察启发我们，我们并不需要计算 。我们只需要计算 这些 的 次幂项。后者可以通过连续平方得到：, , 。

算法流程如下：

1. 初始化结果 res = 1。
2. 遍历 的二进制位，从低到高。
3. 如果 的当前最低位是1，说明最终结果需要乘以当前对应的 项。即 res = res * a。
4. 将 平方，a = a * a，为下一位做准备。
5. 将 右移一位，b = b >> 1，处理下一位。
6. 所有操作都在模 意义下进行。

代码实现:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// 计算 a^b mod p
ll qpow(ll a, ll b, ll p) {
    ll res = 1;
    a %= p; // 初始a就可能大于p
    while (b > 0) {
        if (b & 1) { // 如果b的当前最低位是1
            res = res * a % p; // 乘上当前的a^(2^k)
        }
        a = a * a % p; // a自平方，准备下一轮
        b >>= 1;       // b右移，处理下一位
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll a, b, p;
    cin >> a >> b >> p;
    cout << qpow(a, b, p) << endl;

    return 0;
}

复杂度分析:

• 时间复杂度: 。循环次数取决于 的二进制位数，约为 。

空间复杂度: 。
快速幂是位运算思维的典范应用。它将一个看似线性的问题，通过二进制分解，转化为了对数级的问题。这种“分治”思想，是算法竞赛中的核心能力。

4.2 格雷码：相邻两数仅一位之差的编码

题意概括:
构造一个 位的二进制码序列，从 开始到 结束，共 个码。要求序列中任意两个相邻的码，其二进制表示只有一位不同。这就是格雷码（Gray Code）。例如， 的一种格雷码是 000, 001, 011, 010, 110, 111, 101, 100。

分析:
构造格雷码有多种方法，其中一种基于递归的“反射法”很直观，但效率不高。这里我们介绍一种利用位运算的直接转换法。

核心思想：i 与 i>>1 的异或
一个数 i 的格雷码 g 可以通过一个美妙的公式直接计算：

为什么这个公式有效？
我们来思考当 i 增加1时，g 会如何变化。当 i 变为 i+1 时，i 的二进制表示中，最右边的0变为1，该位右边的所有1变为0。这是一个连锁反应。
例如 i=5 (101) 变成 i=6 (110)。
g(5) = 5 ^ (5>>1) = (101)_2 ^ (010)_2 = (111)_2
g(6) = 6 ^ (6>>1) = (110)_2 ^ (011)_2 = (101)_2
g(5) 和 g(6) 之间，111 和 101，确实只有一位不同。
这个公式的精髓在于，i 的第 k 位和第 k+1 位的关系，通过异或被编码到了 g 的第 k 位。当 i 发生变化时，这种局部依赖关系保证了 g 的变化是最小的。深入的证明需要一些代数推导，但记住这个公式和它的性质，在竞赛中就足够了。

代码实现:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// 本题为生成n位格雷码序列
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    // 遍历所有2^n个数
    for (int i = 0; i < (1 << n); ++i) {
        // 计算i对应的格雷码
        int g = i ^ (i >> 1);
        
        // 以n位二进制串格式输出
        for (int j = n - 1; j >= 0; --j) {
            cout << ((g >> j) & 1);
        }
        cout << '\n';
    }

    return 0;
}

复杂度分析:

• 时间复杂度: 。外层循环 次，内层循环打印 位。这是输出结果所必需的复杂度。
• 空间复杂度: 。

格雷码问题展示了位运算在编码理论中的巧妙应用。i ^ (i >> 1) 这个公式，简洁而深刻，是算法之美的体现。它提醒我们，有时复杂的构造问题，可能存在一个简单的代数对应关系。

4.3 子集生成：二进制与幂集的天然映射

题意概括:
给定一个大小为 的集合（例如，元素为 ），遍历并输出它的所有 个子集。

分析:
这是组合数学中的基本问题，也是状态压缩动态规划（Bitmask DP）的前置技能。

核心思想：整数与子集的同构
一个包含 个元素的集合，其任何一个子集都可以和一个 位的二进制数一一对应。
我们约定，一个 位二进制数 mask，从右到左的第 i 位（0-indexed）为1，表示原集合中的第 i 个元素被包含在该子集中；若为0，则不包含。

例如，集合为 ()：

• 0 = (000)_2 -> {} (空集)
• 1 = (001)_2 -> {A}
• 2 = (010)_2 -> {B}
• 3 = (011)_2 -> {A, B}
• …
• 7 = (111)_2 -> {A, B, C}

因此，遍历 的所有整数，就等价于遍历了该集合的所有子集。

代码实现 1：遍历所有子集

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// 假设元素是 0, 1, ..., n-1
void solve() {
    int n;
    cin >> n;

    // 整数 i 从 0 到 2^n - 1 对应了所有子集
    for (int i = 0; i < (1 << n); ++i) {
        cout << "{ ";
        // 检查 i 的每一位，决定哪个元素在子集中
        for (int j = 0; j < n; ++j) {
            if ((i >> j) & 1) { // 如果第j位是1
                cout << j << " ";
            }
        }
        cout << "}\n";
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

复杂度分析:

• 时间复杂度: 。外层循环 次，内层检查 位。
• 空间复杂度: 。

进阶：遍历一个给定集合的所有子集
在许多问题中，我们不是要遍历全集的子集，而是要遍历一个特定子集（用掩码 s 表示）的所有子集（或称子掩码）。

朴素的方法是 for (int sub = 0; sub < s; ++sub) 然后判断 (sub & s) == sub。但这会检查很多无效的 sub。

高效技巧：(sub - 1) & s

// 遍历 s 的所有非空子集
for (int sub = s; sub; sub = (sub - 1) & s) {
    // sub 是 s 的一个子集
}

原理揭秘：

• sub - 1：这个操作会找到 sub 的最低位的1，把它变成0，并把它右边的所有0都变成1。
• & s：这个操作是关键。它确保了结果仍然是 s 的子集。sub - 1 可能会把 s 中为0的位变成1，但 & s 会把这些“非法”的1全部清零，只保留那些原来就在 s 中的位。

这个迭代方式会以一种不直观但高效的顺序，不重不漏地遍历 s 的所有子集。其循环次数等于 s 的子集个数，即 ，远优于遍历到 s。

代码实现 2：遍历子集的子集

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    int s; // 一个表示集合的掩码
    cin >> s;

    // 假设我们要遍历 s 的所有非空子集
    cout << "Subsets of " << s << " are:\n";
    // 技巧: sub = (sub - 1) & s
    for (int sub = s; sub; sub = (sub - 1) & s) {
        cout << sub << "\n";
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

复杂度分析:

• 时间复杂度: ，其中 是 s 中1的个数。
• 空间复杂度: 。

5. 状态压缩动态规划 (Bitmask DP) — 降维的艺术

如果说前面的技巧是“术”，那么状态压缩动态规划（简称“状压DP”）则是“道”。它是位运算思维与动态规划思想的完美结合，能够解决一类特殊的组合优化问题。当你发现问题的状态可以表示为一个小集合的子集时，状压DP的大门就向你敞开了。

5.1 何时以及为何使用状压DP？

状压DP通常适用于N规模很小（一般 ）的问题。其核心特征是，DP状态中有一维表示了“某些元素的选取情况”或“某些位置的访问状态”。这个“状态”本身就是一个集合。

我们之前已经看到，一个大小为 的集合，其所有子集都可以用一个 位的整数来表示。这就完成了“降维”：将一个复杂的集合状态，压缩（映射）到了一个整数维度。这使得我们可以在DP状态数组中，用一个整数下标来代表一个集合状态，从而进行状态转移。

状压DP的本质，就是把一个指数级的状态空间（ 个子集）通过位运算技巧，纳入到DP的框架中进行高效计算。

5.2 经典范例：旅行商问题 (Traveling Salesperson Problem, TSP)

题意概括:
给定 个城市和它们之间的距离。寻找一条经过每个城市恰好一次，并最终返回起点的最短路径。这是一个著名的NP-hard问题。但当 很小时，我们可以用状压DP解决。

分析:
我们需要记录两个关键信息来进行状态转移：

1. 当前已经访问过的城市集合。
2. 当前所在的城市是哪一个。

这恰好是状压DP的用武之地。

• 状态定义:
  dp[s][i] 表示：当前访问过的城市集合为 s（一个二进制掩码），且最后停留在城市 i 时，所经过的最短路径长度。其中，城市 i 必须在集合 s 中。

• 状态转移:
  要计算 dp[s][i]，我们必须是从 s 中除去 i 的某个城市 j 转移过来的。这个“上一个状态”的城市集合是 s 去掉 i，即 s ^ (1 << i)。
  因此，状态转移方程为：
  
  其中 是从城市 j 到城市 i 的距离。

• 初始化:
  假设我们从城市0出发。初始状态是只访问了城市0，那么 dp[1 << 0][0] = 0。其他所有 dp 值应初始化为无穷大。

• 最终答案:
  遍历完所有城市后，状态掩码为 (1 << N) - 1 (所有位都为1)。我们需要从最后一个城市 i 返回起点城市0。所以最终答案是：
  

代码实现:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 20;
const int INF = 0x3f3f3f3f;

int n;
int w[N][N]; // w[i][j] 存储城市i到j的距离
int dp[1 << N][N];

void solve() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> w[i][j];
        }
    }

    // 初始化dp数组
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0; // 从城市0出发，初始状态集合为{0}，路径长度为0

    // 遍历所有状态集合 s
    for (int s = 1; s < (1 << n); ++s) {
        // 遍历当前状态s的终点城市i
        for (int i = 0; i < n; ++i) {
            if (!((s >> i) & 1)) continue; // i必须在集合s中

            // 遍历上一个状态的终点城市j
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                // j必须在上一个集合 s ^ (1 << i) 中
                if (!((s >> j) & 1)) continue; 

                // 从状态 {s without i, end at j} 转移到 {s, end at i}
                int ps = s ^ (1 << i); // 上一个状态的集合
                if (dp[ps][j] != INF) {
                    dp[s][i] = min(dp[s][i], dp[ps][j] + w[j][i]);
                }
            }
        }
    }

    int ans = INF;
    // 计算最终回到起点0的总路径
    for (int i = 1; i < n; ++i) {
        ans = min(ans, dp[(1 << n) - 1][i] + w[i][0]);
    }
    if (n == 1) ans = 0; // 特判N=1的情况

    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

复杂度分析:

• 时间复杂度: 。状态总数是 ，每个状态的转移需要 的时间。
• 空间复杂度: 。用于存储 dp 数组。

提醒:
状压DP的循环顺序很重要。通常，我们应该将表示集合的掩码 s 作为最外层循环，从小到大遍历。这保证了在计算 dp[s][...] 时，所有比 s 更小的子集的状态 dp[sub][...] 都已经被计算完毕，满足DP的无后效性原则。

6. 位运算与数据结构

位运算的二进制分解思想，深刻地影响了一些高效数据结构的设计。它们利用2的幂次来划分问题，实现了对数级的性能。

6.1 稀疏表 (Sparse Table, ST) 与RMQ问题

题意概括:
给定一个静态数组 。需要回答多个查询，每个查询给出区间 ，要求返回该区间的最小值（或最大值等满足可重复贡献性质的操作）。

分析:
如果允许离线，可以用线段树等数据结构做到 查询。但对于静态数组，我们可以做到更快的 查询，代价是 的预处理。这就是ST表。

核心思想：二进制倍增
ST表的核心是倍增思想。我们预处理出所有形如 的区间的最值。

• 状态定义:
  st[i][j] 表示区间 (即从 i 开始，长度为 ) 的最小值。

• 预处理 (DP):
  长度为 的区间，可以看作是两个相邻的、长度为 的区间的并集。
  
  所以，转移方程为：
  
  基础情况是 st[i][0] = A[i] (长度为 的区间)。

• 查询:
  对于任意查询区间 ，其长度为 len = r - l + 1。我们找到一个最大的 使得 。这个 可以通过 得到。
  然后，我们可以用两个长度为 的区间来覆盖整个 ：

  1. 从 l 开始的区间:
  2. 以 r 结尾的区间:
     这两个区间可能重叠，但对于求最小值、最大值、按位与、按位或、最大公约数这类幂等（或称可重复贡献）操作，重叠部分计算两次不影响结果。
     因此，查询结果为：
     

代码实现:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 5;
const int LOGN = 17; // log2(100000) approx 16.6

int n, q;
int a[N];
int st[N][LOGN + 1];
int lg[N]; // lg[i] = floor(log2(i))

// 预处理
void pre() {
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) {
        lg[i] = lg[i / 2] + 1;
    }
    for (int i = 1; i <= n; ++i) {
        st[i][0] = a[i];
    }
    for (int j = 1; j <= LOGN; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

// O(1) 查询
int ask(int l, int r) {
    int k = lg[r - l + 1];
    return min(st[l][k], st[r - (1 << k) + 1][k]);
}

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    pre();
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << ask(l, r) << "\n";
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

复杂度分析:

• 预处理时间复杂度: 。
• 查询时间复杂度: 。

空间复杂度: 。
ST表是二进制分解思想的又一力证。它将任意区间查询问题，通过2的幂次作为“基”，分解为常数个预处理好的子问题。理解了这一点，你就能明白为何它对操作有“可重复贡献”的要求，而线段树则没有（线段树通过不重不漏的区间剖分，适用于求和等操作）。

6.2 lowbit与树状数组的再回首

在前篇中，我们详细推导了 lowbit(n) = n & -n。现在，让我们将其与树状数组（Fenwick Tree）联系起来。树状数组的精髓在于，其每个节点 c[i] 维护的是原数组中一个特定区间的和。这个区间就是 (i - lowbit(i), i]。

• add(i, val) 操作：更新 i 点后，需要向上更新所有包含 i 的父节点。这些父节点的下标恰好是 i += lowbit(i)。
• query(i) 操作：查询前缀和 [1, i]，需要将 i 分解为若干个 lowbit 区间的和。这些区间的分解方式恰好是 i -= lowbit(i)。

lowbit 不仅是一个计算技巧，它揭示了整数二进制表示的一种内在的层级结构。树状数组正是利用了这种结构，将一维的前缀和问题，映射到了一个隐含的树形结构上，从而实现了高效的单点更新和区间查询。

7. 线性基 — XOR世界的向量空间

这是我们将要探索的、最具数学美感的位运算主题之一。线性基是处理一类关于异或和（XOR sum）问题的强大武器。它源于线性代数的概念，但在算法竞赛中，我们可以用更具操作性的方式来理解它。

类比：
想象一下三维空间中的向量。任何一个向量都可以由基向量 的线性组合表示。线性基在异或的世界里扮演了类似的角色。

定义：
给定一个数集 ，它的线性基是一组最小的数 ，使得 中任何一个数的子集的异或和，都能由 中某个子集的异或和表示出来。换句话说， 的异或空间与 的异或空间相同。

7.1 线性基的构造

我们通常构造一个“三角化”的线性基 b[]，其中 b[i] 要么是0，要么是最高位为 i 的一个数。

构造算法：
遍历原数集 中的每一个数 x。
对于每个 x，从最高位（比如60）向最低位遍历。
假设当前遍历到第 i 位：

1. 如果 x 的第 i 位是0，跳过，检查下一位。
2. 如果 x 的第 i 位是1：
   a. 如果 b[i] 为0，说明 x 在第 i 位上引入了一个新的、无法被现有基表示的“分量”。我们将 x 作为第 i 维的基，令 b[i] = x，然后结束对 x 的处理。
   b. 如果 b[i] 不为0，说明第 i 位的“分量”已经可以由 b[i] 表示。为了消除 x 的第 i 位，我们令 x = x ^ b[i]。这样 x 的第 i 位就变成了0，然后我们继续用这个新的 x 去检查更低的位。

如果一个数 x 在这个过程中被消成了0，说明它可以被当前的线性基完全表示，它没有带来任何新信息。

代码实现:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int D = 60; // long long 最多到60位左右
ll b[D + 1]; // 线性基数组 b[i]是最高位为i的基

void ins(ll x) {
    for (int i = D; i >= 0; --i) {
        if (!((x >> i) & 1)) continue; // x的第i位是0，跳过
        if (!b[i]) { // 基b[i]为空
            b[i] = x;
            return;
        }
        x ^= b[i]; // 否则用b[i]消掉x的第i位
    }
    // 如果x最后变成0，说明它能被基表示，不需要插入
}

void solve() {
    int n;
    cin >> n;
    memset(b, 0, sizeof(b));
    for (int i = 0; i < n; ++i) {
        ll x;
        cin >> x;
        ins(x);
    }
    // ... 之后可以进行查询
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

7.2 线性基的应用

构造好的线性基有许多强大的用途。

1. 查询子集最大异或和
题意概括: 从给定数集中选出任意个数，使得它们的异或和最大。

方法:
从最高位 D 向最低位遍历线性基。对于每个 b[i]，贪心地尝试让答案的第 i 位变成1。
初始化 res = 0。从 i = D 到 0：
如果 (res ^ b[i]) > res，则 res = res ^ b[i]。
这等价于 if (!((res >> i) & 1)) res ^= b[i]，但前者更简洁。

为什么这是对的？
因为我们的基是三角化的。当我们考虑第 i 位时，b[i] 是唯一一个最高位为 i 的基。用它去更新 res，只会影响 res 的第 i 位及更低的位，不会影响我们已经做出的更高位的贪心决策。因此，从高到低贪心，保证了结果最优。

代码实现:

// 在已构造好线性基b[]的基础上
ll qmax() {
    ll res = 0;
    for (int i = D; i >= 0; --i) {
        if ((res ^ b[i]) > res) {
            res = res ^ b[i];
        }
    }
    return res;
}

2. 查询子集第k小异或和
这稍微复杂一些，需要对基进行进一步处理，使其成为一个更完美的“对角”基。

步骤:

1. 重构基: 对已经构造好的三角基 b，从高到低遍历 i。对于每个非零的 b[i]，再从 i-1 到 0 遍历 j。如果 b[i] 的第 j 位是1，则 b[i] ^= b[j]。这样操作后，每个 b[i] 的最高位是 i，且对于任意 j != i，b[i] 的第 j 位如果想为1，则 b[j] 必须是0。
2. 筛选有效基: 将所有非零的基向量放入一个新数组 p 中。
3. 查询: 将 k 进行二进制拆分。如果 k 的第 i 位（从0计）是1，则将答案异或上 p[i]（p中第 i 小的基）。

3. 查询一个数 v 能否被异或出来
将 v 插入线性基。如果在插入过程中 v 变成了0，则说明 v 可以被原线性基表示出来。否则，v 不能被表示。

代码示例：P3812 [模板]线性基

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int D = 50; // 题目数据范围
ll b[D + 1];

void ins(ll x) {
    for (int i = D; i >= 0; --i) {
        if (!((x >> i) & 1)) continue;
        if (!b[i]) {
            b[i] = x;
            return;
        }
        x ^= b[i];
    }
}

ll qmax() {
    ll res = 0;
    for (int i = D; i >= 0; --i) {
        res = max(res, res ^ b[i]);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    memset(b, 0, sizeof(b));
    for (int i = 0; i < n; ++i) {
        ll x;
        cin >> x;
        ins(x);
    }
    
    cout << qmax() << endl;

    return 0;
}

复杂度分析:

• 构造 (插入): 每次插入一个数，最多需要 ，其中 是数值上限。总构造时间为 。
• 查询最大值: 。
• 空间复杂度: 。

线性基是位运算与线性代数思想交汇的产物。它将一组数的异或问题，转化为了对一个极小子集（基）的操作。掌握线性基，意味着你能在处理异或问题时，从一个全新的、更高维的视角去思考，这是冲击高水平竞赛所必需的能力。

8.写在最后

当你面对一个问题，特别是与集合、状态、计数、优化相关的问题时，不妨在脑海里多问一句：这个问题能否用二进制的视角来重新审视？它的状态能否被压缩？它的运算是否具有某种奇特的代数性质？

附录：例题选讲

P1225 黑白棋游戏

题目描述

黑白棋游戏的棋盘由 方格阵列构成。棋盘的每一方格中放有 枚棋子，共有 枚白棋子和 枚黑棋子。这 枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有 条公共边的 个方格称为相邻方格。一个方格最多可有 个相邻方格。在玩黑白棋游戏时，每一步可将任何 个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态，编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。

输入格式

输入文件共有 行。前四行是初始游戏状态，后四行是目标游戏状态。每行 个数分别表示该行放置的棋子颜色。“ ”表示白棋；“ ”表示黑棋。

输出格式

输出文件的第一行是着棋步数 。接下来 行，每行 个数分别表示该步交换棋子的两个相邻方格的位置。例如，abcd 表示将棋盘上 处的棋子与 处的棋子换位。

输入输出样例 #1

输入 #1

1111
0000
1110
0010
1010
0101
1010
0101

输出 #1

4
1222
1424
3242
4344

P1896 [SCOI2005] 互不侵犯

题目描述

在 的棋盘里面放 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 个格子。

输入格式

只有一行，包含两个数 。

输出格式

所得的方案数

输入输出样例 #1

输入 #1

3 2

输出 #1

16

说明/提示

数据范围及约定

对于全部数据，，。

P1225 黑白棋游戏

题目分析与解题思路

棋盘压缩成 16 位无符号整数：第 行第 列对应第 位，1 表黑棋、0 表白棋，从输入构造起始状态 s 和目标状态 t。随后在最多 个状态的完整图上做单向 BFS：用循环数组 que 做队列，vs 标记访问，pr 记录前驱状态，mv 记录“由哪两个格交换而来”（高 4 位存第一个格下标，低 4 位存第二个）。扩展时枚举 16 个格子及其四个相邻格，只要两格颜色不同就可交换，新状态通过 cur ^ (1<<p) ^ (1<<q) 得到；若未访问则入队并保存路径信息。第一次弹出目标状态时即得到最短步数，然后从 t 沿 pr 回溯至 s 收集交换编码，反转后按行列从 1 开始输出，每步打印四位数 abcd 表示交换 与 。状态总量仅 个，BFS 扫描复杂度约 ，四个 65 536 长度数组加队列占不到 300 KB，故时间、空间都绰绰有余，且保证输出的一定是一条最短交换序列。

代码实现

#include<bits/stdc++.h>
using namespace std; using ll=long long;

int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1};

static uint16_t que[65536], pr[65536];   // BFS 队列与前驱
static unsigned char vs[65536], mv[65536]; // 访问标记与产生该状态的交换

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    uint16_t s=0, t=0;
    string str;
    for(int i=0;i<4;i++){                // 读初始状态
        cin>>str;
        for(int j=0;j<4;j++)
            if(str[j]=='1') s|=1<<(i*4+j);
    }
    for(int i=0;i<4;i++){                // 读目标状态
        cin>>str;
        for(int j=0;j<4;j++)
            if(str[j]=='1') t|=1<<(i*4+j);
    }

    int hd=0, tl=0;                      // BFS
    que[tl++]=s; vs[s]=1; pr[s]=65535;
    while(hd<tl){
        uint16_t cur=que[hd++];
        if(cur==t) break;
        for(int p=0;p<16;p++){
            int r=p/4, c=p%4;
            for(int d=0; d<4; d++){
                int nr=r+dx[d], nc=c+dy[d];
                if(nr<0||nr>=4||nc<0||nc>=4) continue;
                int q=nr*4+nc;
                if(((cur>>p)&1)==((cur>>q)&1)) continue; // 相同颜色交换无效
                uint16_t nxt=cur^(1<<p)^(1<<q);          // 仅两位不同，异或即可
                if(vs[nxt]) continue;
                vs[nxt]=1; pr[nxt]=cur; mv[nxt]=(p<<4)|q; // 记录路径
                que[tl++]=nxt;
            }
        }
    }

    vector<uint16_t> path;               // 回溯最短序列
    for(uint16_t x=t; x!=s; x=pr[x]) path.push_back(mv[x]);
    reverse(path.begin(), path.end());

    cout<<path.size()<<"\n";
    for(auto code:path){
        int p=code>>4, q=code&15;
        cout<<p/4+1<<p%4+1<<q/4+1<<q%4+1<<"\n";
    }
    return 0;
}

P1896 [SCOI2005] 互不侵犯

题目分析与解题思路

1. 问题定性：网格图上的组合计数DP
题目要求在 棋盘上放 个国王，求总方案数。国王的攻击范围是周围8个格子。这是一个带有局部约束的组合计数问题。 的范围很小（），这是状态压缩DP的强烈信号。

2. DP设计：逐行放置
我们可以一行一行地来放置国王，并进行DP。

• 状态定义：dp[i][j][s] 表示在前 i 行，共放置了 j 个国王，且第 i 行的放置状态为 s 时的方案数。s 是一个N位二进制数，第k位为1表示第k列放了国王。

• 状态的合法性:

  1. 行内合法性：国王不能左右相邻。一个状态 s 是行内合法的，当且仅当 s 的二进制表示中没有连续的1。这可以用 (s & (s << 1)) == 0 来判断。
  2. 行间合法性：第 i 行的状态 s 和第 i-1 行的状态 ps 必须兼容。这意味着 s 中任何一个国王都不能被 ps 中的国王攻击。
     • s & ps == 0 (正上方没有国王)
     • s & (ps << 1) == 0 (左上方没有国王)
     • s & (ps >> 1) == 0 (右上方没有国王)

• 状态转移方程:
  dp[i][j][s] 的值，可以由所有与 s 兼容的、合法的上一行状态 ps 转移而来。
  
  其中，ps 必须是行内合法的，且与 s 满足行间合法性。popcount(s) 是 s 中1的个数，即当前行放置的国王数。

3. 实现细节与优化

• 预处理合法状态: 我们可以预先计算出所有行内合法的状态 s 及其对应的国王数 popcount(s)，存入一个数组中。这样在DP转移时，我们只需要遍历这些预处理好的合法状态，而不是从 0到 (1<<N)-1，可以节省大量时间。
• DP初始化: 我们引入一个“第0行”，它只有一个状态（不放任何国王，s=0），国王数为0，方案数为1。即 dp[0][0][0] = 1。这使得DP的递推可以从第1行开始，形式统一。
• 最终答案: 最终答案是所有在第 N 行放置了总共 K 个国王的方案数之和，即 。

代码实现

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n, k;
vector<int> st; // 存储所有合法的单行状态
vector<int> num; // 存储对应状态的国王数
ll dp[10][100][1 << 9];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> k;

    // 预处理所有合法的单行状态
    for (int i = 0; i < (1 << n); ++i) {
        if (!(i & (i << 1))) { // 左右不相邻
            st.push_back(i);
            num.push_back(__builtin_popcount(i));
        }
    }

    dp[0][0][0] = 1; // 哨兵：第0行，0个国王，状态为0，方案数为1

    // 逐行DP
    for (int i = 1; i <= n; ++i) { // 当前行
        for (int j = 0; j <= k; ++j) { // 总国王数
            for (size_t a = 0; a < st.size(); ++a) { // 枚举当前行i的合法状态s
                int s = st[a];
                int c = num[a]; // 当前行状态s的国王数
                
                if (j < c) continue; // 总国王数必须不小于当前行的国王数

                for (size_t b = 0; b < st.size(); ++b) { // 枚举上一行i-1的合法状态ps
                    int ps = st[b];
                    
                    // 行间兼容性检查
                    if ((s & ps) == 0 && (s & (ps << 1)) == 0 && (s & (ps >> 1)) == 0) {
                        dp[i][j][s] += dp[i - 1][j - c][ps];
                    }
                }
            }
        }
    }

    ll ans = 0;
    // 统计最终答案
    for (size_t i = 0; i < st.size(); ++i) {
        ans += dp[n][k][st[i]];
    }
    cout << ans << endl;

    return 0;
}

复杂度分析

• 时间复杂度: ，其中 是单行合法状态的数量。 的数量级大约是斐波那契数 ，对于 来说是个很小的常数。所以复杂度是可接受的。
• 空间复杂度: ，主要由 dp 数组决定。

这道题是状压DP的入门和经典模板。它完美地展示了如何将一个二维网格问题，通过逐行递推和位运算压缩行状态，转化为一个多维DP问题。预处理合法状态是此类问题的一个常用优化，而dp[0][0][0]=1的哨兵初始化则是简化代码逻辑的优雅技巧。