专题- 对数之桥：二进制的算法之美

# 对数之桥：二进制的算法之美

从数学本质到工程智慧，揭示算法背后的统一基石

---

## 目录

1. 数学之根：二进制分解定理
2. 二进制的集合观——状压DP的物理外挂
3. 算法之核：分治与倍增的对偶
4. 二分查找——分治的直观体现
5. 快速幂——倍增的经典应用
6. 倍增法（树上LCA）——空间换时间
7. 矩阵快速幂与哈希优化
8. ST表——倍增的静态版本
9. 多重背包的二进制拆分
10. 结构之魂：线性访问的对数化
11. 二进制堆——隐式树的极致简洁
12. 树状数组——lowbit 的魔法
13. 线段树——区间二分递归划分
14. 信奥数据结构三板斧——赛场选型决策表
15. 实战对标：同一道题，两种写法
16. 状压DP——二进制表示集合
17. 信奥心法：复杂度分析与套路识别
18. 结尾

---

## 01. 数学之根：二进制分解定理

一切高效算法的起点，源于对整数内在结构的深刻洞察。

---

### 核心定理

任何正整数 $n$ 都可唯一表示为 $2^k$ 的幂次方之和：

$$n = \sum b_k \cdot 2^k, \quad b_k \in \{0, 1\}$$

---

### 三重意义（信奥视角）

- **分治的源泉**：大问题拆解为若干 $2^k$ 子问题（自顶向下）
- **组合的基础**：子问题解通过 $2^k$ 项重组（自底向上）
- **硬件的契合**：位运算（`<<`、`>>`、`&`、`|`）是 CPU 最高效指令，算法天然与硬件协同

💡 **一句话精髓**：二进制分解是连接抽象数学与物理硬件的桥梁，是所有 $O(\log N)$ 优化的理论根基。

---

## 02. 二进制的集合观——状压DP的物理外挂

整数不仅能表示"数量"，更能表示"**状态**"（集合）。

### 核心映射

用一个 `int` 的二进制位 0/1 表示某个元素是否被选中：

- `1010₂` = 选中第1和第3个元素（从低位起）
- 位运算即 $O(1)$ 的集合操作：
  - `A | B` → 并集
  - `A & B` → 交集
  - `A ^ B` → 对称差
  - `~A` → 补集

### 赛场必杀技：枚举子集

```cpp
for (int s = t; s; s = (s - 1) & t) {
    // s 是 t 的所有非空子集
}
```

💡 **信奥直觉**：看到数据范围 $N \le 20$，**立刻反射**——状压DP！$2^N$ 约百万级，完全可行。

---

## 03. 算法之核：分治与倍增的对偶

二进制分解在算法设计中呈现出两种截然相反却又高度统一的策略：

- **分治** = 自顶向下地"拆"（按高位到低位）
- **倍增** = 自底向上地"合"（按低位到高位）

> 同一枚硬币的两面，同源异流。

---

## 04. 二分查找——分治的直观体现

**痛点**：有序数组线性扫描 $O(N)$，$10^5$ 规模勉强，$10^7$ 直接超时。

**方案**：每次比较中间元素，排除一半搜索空间。本质上是在**逐位确定目标索引的二进制表示**。

**复杂度**：$O(\log N)$

### 信奥模板题：P2249 【深基13.例1】查找

```cpp
int l = 1, r = n, ans = -1;
while (l <= r) {
    int mid = (l + r) >> 1;
    if (a[mid] >= x) {   // 找第一个 >= x 的位置
        ans = mid;
        r = mid - 1;
    } else {
        l = mid + 1;
    }
}
```

---

### 🔥 避坑指南

💡 **精髓**："猜数字的终极奥义——每一次猜测都在确定一个二进制位。写二分前先想清楚：**找第一个满足条件的，还是最后一个？**"

---

## 05. 快速幂——倍增的经典应用

**痛点**：计算 $a^n$ 需 $n$ 次乘法，$n$ 为大整数（如 $10^9$）时完全不可行。

**方案**：预计算 $a^1, a^2, a^4, a^8...$，将指数 $n$ 按二进制拆分后组合。

**示例**：$a^{13} = a^8 \cdot a^4 \cdot a^1$（仅需 $O(\log N)$ 次乘法）

### 信奥模板题：P1226 【模板】快速幂

```cpp
long long qpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
```

💡 **精髓**："指数的二进制拆分，让乘法次数从线性坍缩为对数。"

---

## 06. 倍增法（树上LCA）——空间换时间

**痛点**：树上查询两点最近公共祖先（LCA），朴素逐级上跳最坏 $O(N)$。

**方案**：预处理 `fa[u][k]` 表示节点 $u$ 向上 $2^k$ 层的祖先。

**复杂度**：$O(N \log N)$ 预处理 + $O(\log N)$ 查询

### 信奥模板题：P3379 【模板】最近公共祖先（LCA）

```cpp
// 预处理：BFS/DFS 求 depth 和 fa[u][0]
for (int k = 1; k <= LOG; k++)
    for (int u = 1; u <= n; u++)
        fa[u][k] = fa[fa[u][k-1]][k-1];

// 查询 LCA
int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    // 第一步：u 上跳到与 v 同深度（必须从高位向低位贪心！）
    for (int k = LOG; k >= 0; k--)
        if (depth[u] - (1 << k) >= depth[v])
            u = fa[u][k];
    if (u == v) return u;
    // 第二步：u 和 v 一起上跳
    for (int k = LOG; k >= 0; k--)
        if (fa[u][k] != fa[v][k])
            u = fa[u][k], v = fa[v][k];
    return fa[u][0];
}
```

---

### 🔥 避坑指南

**为什么倒着循环？** 凑 13（1101），必须先拿 8，再拿 4，最后拿 1。先拿 1 就凑不出来了！

💡 **精髓**："用预计算的 $2^k$ 级台阶，实现 $\log N$ 倍提速。"

---

## 07. 矩阵快速幂与哈希优化

**矩阵快速幂**：
将快速幂扩展到矩阵域，把线性递推（如斐波那契）从 $O(N)$ 优化至 $O(K^3 \log N)$。处理 $N \le 10^{18}$ 的递推题，这是唯一解。

### 信奥经典题：P1962 斐波那契数列

```cpp
struct Matrix {
    long long a[2][2];
    Matrix operator * (const Matrix& other) { /* ... */ }
};

Matrix qpow(Matrix a, long long n) {
    Matrix res = {1, 0, 0, 1};  // 单位矩阵
    while (n) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}
// 答案 = qpow(M, n).a[0][1];
```

---

**哈希表优化（常数级神技）**：
当哈希表容量 `size` 恰好为 $2^k$ 时：
- `hash % size` 等价于 `hash & (size - 1)`
- 用位运算替代除法取模，消除高频访问的性能瓶颈

💡 **精髓**："与硬件对话，让常数降到最低。"

---

## 08. ST表——倍增的静态版本

**定位**：RMQ（区间最值查询）的终极答案，**只适合无修改场景**。

**方案**：预处理 `st[k][i]` 表示从 i 开始长度为 $2^k$ 的区间最值。查询时取两端覆盖区间的最值合并。

**复杂度**：$O(N \log N)$ 预处理 + $O(1)$ 查询

### 信奥模板题：P3865 【模板】ST 表

```cpp
// 预处理 log2
lg[1] = 0;
for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;

// 预处理 ST 表
for (int k = 1; k <= lg[n]; k++)
    for (int i = 1; i + (1 << k) - 1 <= n; i++)
        st[k][i] = max(st[k-1][i], st[k-1][i + (1 << (k-1))]);

// 查询 [l, r] 最大值
int len = r - l + 1;
int k = lg[len];
int ans = max(st[k][l], st[k][r - (1 << k) + 1]);
```

---

💡 **精髓**："倍增思想最纯粹的应用——不做修改，只做快速回答。"

---

## 09. 多重背包的二进制拆分

> 这是二进制分解在 DP 中的直接应用，普及组/提高组必考！

**痛点**：有 $s$ 个价值相同的物品，若拆成 $s$ 个 0/1 物品做背包，复杂度 $O(N \cdot S \cdot V)$，直接炸裂。

**方案**：将 $s$ 拆分为 $1, 2, 4, ..., 2^k, r$（$r$ 为剩余部分）。$s$ 以内的任意数量均可由这些二进制块组合而成。

**示例**：$s = 13$ → 拆为 $1, 2, 4, 6$（$1+2+4=7$，剩余 $6$）
- 需要 5 → 1 + 4，需要 12 → 2 + 4 + 6

---

### 信奥模板题：P1776 宝物筛选（多重背包模板）

```cpp
for (int i = 1; i <= n; i++) {
    int v, w, s;
    cin >> v >> w >> s;
    // 二进制拆分
    for (int k = 1; k <= s; k <<= 1) {
        s -= k;
        items.push_back({v * k, w * k});
    }
    if (s > 0) items.push_back({v * s, w * s});
}
// 拆分完后对 items 做 0/1 背包即可
```

**复杂度**：从 $O(N \cdot S \cdot V)$ 骤降至 $O(N \cdot \log S \cdot V)$

💡 **精髓**："用 $\log S$ 个二进制块替代 $S$ 个原始物品，降维打击。"

---

## 10. 结构之魂：线性访问的对数化

数据结构是算法的物理载体。以下结构将二进制分解定理具象化为高效的存储与访问模式，共同目标是**打破线性访问的桎梏**。

---

## 11. 二进制堆——隐式树的极致简洁

**痛点**：优先队列需要动态维护最值，普通数组插入/删除最值需 $O(N)$。

**方案**：利用完全二叉树性质，用数组下标关系隐式构建树：
- 左孩 = $2i$
- 右孩 = $2i+1$
- 父 = $i//2$

**复杂度**：插入/删除堆顶仅需 $O(\log N)$ 次层级跳跃。

---

### C++ STL 直接可用
```cpp
#include <queue>
priority_queue<int> q;                    // 大根堆
priority_queue<int, vector<int>, greater<int>> q;  // 小根堆
```

### 手写堆（竞赛常用）
```cpp
void push(int x) {
    heap[++sz] = x;
    for (int i = sz; i > 1 && heap[i] < heap[i >> 1]; i >>= 1)
        swap(heap[i], heap[i >> 1]);
}
void pop() {
    heap[1] = heap[sz--];
    for (int i = 1; (i << 1) <= sz; ) {
        int son = i << 1;
        if (son < sz && heap[son + 1] < heap[son]) son++;
        if (heap[son] >= heap[i]) break;
        swap(heap[son], heap[i]);
        i = son;
    }
}
```

💡 **精髓**："无需指针，仅靠下标的二进制移位，便构建出高效的优先队列。"

---

## 12. 树状数组——`lowbit` 的魔法

**痛点**：频繁的单点更新与前缀和查询，朴素方法无法兼顾。

**方案**：`lowbit(x) = x & -x` 将索引拆分为多个 $2^k$ 长度区间。

**复杂度**：更新与查询均为 $O(\log N)$

### 信奥模板题：P3374 【模板】树状数组 1

```cpp
int lowbit(int x) { return x & -x; }

void add(int idx, int val) {
    for (; idx <= n; idx += lowbit(idx)) tr[idx] += val;
}

int sum(int idx) {
    int res = 0;
    for (; idx > 0; idx -= lowbit(idx)) res += tr[idx];
    return res;
}
// 区间查询 [l, r] = sum(r) - sum(l-1)
```

---

### 信奥经典题：P1908 逆序对

```cpp
// 离散化 + 树状数组统计逆序对
for (int i = 1; i <= n; i++) {
    ans += i - 1 - sum(a[i]);  // 前面比 a[i] 大的数
    add(a[i], 1);
}
```

💡 **精髓**："一个位运算定义节点管辖范围，实现更新与查询的完美平衡。"

---

## 13. 线段树——区间二分递归划分

**痛点**：复杂区间操作（区间加、区间赋值、区间求和/最值/染色）需要灵活的数据结构。

**方案**：区间递归对半分割，任意查询区间覆盖为 $O(\log N)$ 个标准节点。

**权衡**：功能强但代码量大（树状数组 3~5 倍码量），常数也更大。

---

### 信奥模板题：P3372 【模板】线段树 1（区间加 + 区间求和）

```cpp
void push_up(int u) { sum[u] = sum[u<<1] + sum[u<<1|1]; }

void push_down(int u, int l, int r) {
    if (!tag[u]) return;
    int mid = (l + r) >> 1;
    sum[u<<1] += tag[u] * (mid - l + 1);
    sum[u<<1|1] += tag[u] * (r - mid);
    tag[u<<1] += tag[u];
    tag[u<<1|1] += tag[u];
    tag[u] = 0;
}

void update(int u, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        sum[u] += val * (r - l + 1);
        tag[u] += val;
        return;
    }
    push_down(u, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) update(u<<1, l, mid, ql, qr, val);
    if (qr > mid) update(u<<1|1, mid+1, r, ql, qr, val);
    push_up(u);
}

long long query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sum[u];
    push_down(u, l, r);
    int mid = (l + r) >> 1;
    long long res = 0;
    if (ql <= mid) res += query(u<<1, l, mid, ql, qr);
    if (qr > mid) res += query(u<<1|1, mid+1, r, ql, qr);
    return res;
}
```

---

### 进阶题目
- **P3373** 【模板】线段树 2（区间加 + 区间乘）
- **P4513** 小白逛公园（区间最大子段和）

💡 **精髓**："区间的二进制分解，是线段树强大功能的基石。"

---

## 14. 信奥数据结构三板斧——赛场选型决策表

| 数据结构 | 核心操作 | 预处理 | 单次操作 | 代码量 | 信奥模板题 | 何时选用 |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| **树状数组** | 单点加 + 前缀和 | $O(N)$ | $O(\log N)$ | ⭐⭐ 30行 | P3374、P1908 | 只需维护**可减信息**（和、异或），无区间赋值 |
| **线段树** | 区间加/赋值 + 区间最值/求和 | $O(N)$ | $O(\log N)$ | ⭐⭐⭐⭐ 120行 | P3372、P3373 | 遇到**区间赋值/取反/染色**等不可减操作 |
| **ST表** | 静态区间最值（RMQ） | $O(N \log N)$ | $O(1)$ | ⭐⭐ 30行 | P3865 | **无修改** + 查询次数 $\gg N$ |

---

💡 **赛场铁律**："**树状数组能做的，线段树一定能做；但线段树代码是树状数组的 3 倍长。** 能树状数组就树状数组，必须区间赋值才上线段树。"

---

## 15. 实战对标：同一道题，两种写法

以 **【模板】动态求逆序对**（单点修改 + 查询前缀和）为例：

**树状数组解法**：30行，$O(\log N)$，轻松过 $10^5$ 数据

```cpp
// 完整代码见第12页
add(pos, delta);
ans = sum(r) - sum(l-1);
```

**线段树解法**：120行，同样是 $O(\log N)$，但常数更大

```cpp
// 完整代码见第13页
update(1, 1, n, pos, pos, delta);
ans = query(1, 1, n, l, r);
```

---

**赛场决策**：如果题目只要求单点修改+前缀查询，树状数组是第一选择。线段树的舞台在"区间赋值、区间覆盖、区间取反"——这些操作树状数组做不了，只能线段树硬刚。

💡 **学会做减法**："多掌握一种数据结构，不是让你杀鸡用牛刀，而是让你在杀牛时恰好有牛刀。"

---

## 16. 状压DP——二进制表示集合

**识别信号**：数据范围 $N \le 20$（$2^N$ 约百万级，可行）

### 信奥经典题：P1171 售货员的难题（TSP简化版）

```cpp
// dp[s][i]：已访问集合 s，当前在 i 点的最短路径
int dp[1 << N][N];
memset(dp, 0x3f, sizeof(dp));
dp[1 << 0][0] = 0;

for (int s = 0; s < (1 << n); s++) {
    for (int i = 0; i < n; i++) {
        if (!(s & (1 << i))) continue;
        for (int j = 0; j < n; j++) {
            if (s & (1 << j)) continue;
            dp[s | (1 << j)][j] = min(dp[s | (1 << j)][j], dp[s][i] + dist[i][j]);
        }
    }
}
// 答案 = min(dp[(1<<n)-1][i] + dist[i][0])
```

---

### 必杀技：枚举子集

```cpp
for (int s = t; s; s = (s - 1) & t) {
    // 枚举 t 的所有非空子集，$O(3^N)$ 总复杂度
}
```

### 信奥经典题：P1896 [SCOI2005] 互不侵犯（状压DP入门）

```cpp
// 预处理每行合法状态（无相邻1）
for (int s = 0; s < (1 << n); s++) {
    if (s & (s << 1)) continue;
    ok[++cnt] = s;
    popcnt[cnt] = __builtin_popcount(s);
}
// dp[行][已放国王数][状态] 逐行转移
```

💡 **赛场反射**："看到 $N \le 20$，**立刻反射——状压DP！** "

---

## 17. 信奥心法：复杂度分析与套路识别

从具体技术中抽离，我们看到的不仅是工具，更是信息学竞赛的**得分密码**。

---

### 如何一眼识别算法？——三个反射弧

---

### 抽象即效率

通过将索引抽象为二进制位、将区间抽象为标准节点、将数量抽象为二进制块，我们发现数据的内在规律，设计出远超朴素方法的算法。

**终极启示：**
算法之美，不在于技巧的繁复，而在于用最朴素的数学原理，解决最复杂的工程问题。

> 二进制分解定理，正是"大道至简"的最佳注脚。

**送给你们的话：**
"看见 $\log N$ 想二分，看见 $2^k$ 想倍增，看见区间加想树状数组，看见区间覆盖想线段树，看见 $N \le 20$ 立刻想状压。把这页PPT刻在脑子里，**提高组一等奖，就在眼前。** "

---

## 18. 结尾

**谢谢观看**