prefix
算法中的“前缀”专题，通常包括一些围绕字符串、数组和树结构的算法与数据结构，这些算法利用“前缀”的特性来优化计算，常见的方向有：
1. 前缀和（Prefix Sum）
前缀和是一种用于快速求数组区间和的技巧。
基本思想：
构建一个前缀和数组 prefix，使得 prefix[i] 表示数组前 i 个元素的总和： [ \text{prefix}[i] = \text{prefix}[i-1] + \text{nums}[i] ] 通过公式快速计算区间和： [ \text{sum}(i, j) = \text{prefix}[j] - \text{prefix}[i-1] ]
经典应用：
- 求子数组的和：如寻找子数组和为固定值的所有子数组。
- 动态区间查询：如某个区间的和是否满足条件。
2. 前缀树（Trie）
前缀树是一种树形数据结构，用于快速查找具有相同前缀的字符串。
基本操作：
- 插入：将一个字符串插入到树中。
- 查询：判断一个字符串是否存在。
- 前缀搜索：查找所有以某个字符串为前缀的单词。
应用场景：
- 自动补全：搜索引擎中的推荐词。
- 词频统计：结合额外的权重存储频率。
- 拼写检查。
3. KMP 算法
KMP（Knuth-Morris-Pratt）是一种用于字符串匹配的算法，核心是构建“部分匹配表”（又称前缀表）。
核心思想：
通过部分匹配表记录每个位置的前缀和后缀的最长公共元素长度，避免重复匹配。
应用场景：
- 子字符串匹配：高效搜索一个字符串是否为另一个字符串的子串。
4. 前缀积（Prefix Product）
类似于前缀和，但用于快速计算数组的区间乘积。
核心公式：
构建前缀积数组 prefix_product： [ \text{prefix_product}[i] = \text{prefix_product}[i-1] \times \text{nums}[i] ] 区间乘积： [ \text{product}(i, j) = \frac{\text{prefix_product}[j]}{\text{prefix_product}[i-1]} ]
5. LCP（最长公共前缀）
查找字符串数组中所有字符串的最长公共前缀。
算法实现：
- 纵向扫描法：逐个字符比较每个字符串。
- 横向扫描法：两两比较，减少比较范围。
- 分治法：递归地分割字符串数组，合并结果。
- 字典树法：利用前缀树构建后寻找最深的公共路径。
6. 前缀 XOR
用于快速求异或操作的区间和。
核心公式：
构建前缀异或数组 prefix_xor： [ \text{prefix_xor}[i] = \text{prefix_xor}[i-1] \oplus \text{nums}[i] ] 区间异或： [ \text{xor}(i, j) = \text{prefix_xor}[j] \oplus \text{prefix_xor}[i-1] ]
7. 动态规划中的前缀思想
动态规划经常利用前缀性质，减少重复计算：
- 子问题的解依赖于前缀状态。
- 如最长递增子序列的 DP 转移可以利用前缀最大值。
如果您有某一方向的具体需求或题目，可以详细讨论和实现！