Hexo

序列与区间处理 (Sequence & Range Processing)

这种方法用于将一个“朴素”的 O(n²) 解法优化到 O(n)。

在我们的算法题中, 可能会遇到两类问题： - 区间查询 (Range Query)：频繁地询问“数组 i 到 j 之间的和/积/异或值是多少？” - 区间更新 (Range Update)：频繁地操作“把数组 i 到 j 之间的所有数都加上 k。”

如果你对每一次“查询”或“更新”都老老实实地跑一个 for 循环，那么每次操作都是 O(n)， q 次操作就是 O(nq)，这通常会超时。

下面是两种常见且互逆的优化技巧：

前缀和

前缀和 (Prefix Sum)一般用于快速区间查询。 - 原理：花费 O(n) 时间预处理一个prefixSum数组。 - 效果：之后每一次区间查询都降为 O(1) 时间。

例如, 给定一个数组 nums，假如题目要求你频繁地计算子数组 nums[i…j]（闭区间）的和或者相关信息, 此时不急着直接入手, 我们可以构建一个前缀和数组 prefixSum 来预处理，其中 prefixSum[i] 存储 nums[0…i-1]（从第0个到第 i − 1 个元素）的总和。

那么，nums[i…j]（闭区间）的和 sum(i, j) 是多少？ - sum(i, j) = (前 j 个元素的和) − (前 i − 1 个元素的和) - sum(i, j) = prefixSum[j + 1] − prefixSum[i]

这样，我们用 O(n) 预处理，换来了 O(1) 的查询。

再比如, 问题变为“和为 K 的子数组有多少个？” 这个问题等价于：找到多少对 (i, j) 使得 sum(i, j) = K。

用前缀和公式代入：prefixSum[j + 1] − prefixSum[i] = K。 变换一下：prefixSum[i] = prefixSum[j + 1] − K。

这成为了一个“两数之和”问题！这就是“枚举右，维护左”的完美应用： - 枚举右 (j)：我们遍历数组，计算出当前的 prefixSum[j+1]（记为 current_sum）。 - 提问：我们需要在 j 的左边找到一个 i，使得 prefixSum[i] = current_sum - K。 - 维护左：我们使用一个哈希表 memo 来存储所有历史上的 prefixSum 值及其出现的次数。

例题: 给定一个整数数组 nums 和一个整数 K，请你统计并返回该数组中和为 K 的子数组的个数。(LC 560 和为 K 的子数组个数)

int subarraySum(std::vector<int>& nums, int k) {
    // 步骤 1: 初始化哈希表
    // 键(Key): 某个前缀和
    // 值(Value): 该前缀和出现的次数
    std::unordered_map<int, int> memo;

    // 步骤 2: 关键初始化
    // 放入 (0, 1) 来处理从索引 0 开始的子数组
    // 解释: 如果 nums[0...j] 的和恰好为 k,
    // 那么 current_sum = k, needed = k - k = 0。
    // 我们需要 memo.count(0) 为 true。
    memo[0] = 1;

    int current_sum = 0;
    int total_count = 0;

    // 步骤 3 & 4: 一次循环 - 提问、查找、维护
    for (int num : nums) {
        // a. 更新状态: (枚举右)
        current_sum += num;

        // b. 提问: 我们需要找的左侧前缀和是什么？
        int needed = current_sum - k;

        // c. 查找: 左侧存在吗？
        // 我们在 map 中查找是否存在键(key)为 needed
        if (memo.count(needed)) {
            // 如果存在，说明找到了一个或多个以 num 结尾的
            // 且和为 k 的子数组。
            total_count += memo[needed];
        }

        // d. 维护: (维护左)
        // 把当前的前缀和存入 map，供后续的元素查找
        memo[current_sum]++;
    }

    return total_count;
}

如果更一般的, 我们会两次遍历 (Two-pass)，提前预处理 - 第一次遍历 (预处理)：创建一个 std::vector prefixSum，prefixSum[i] 存储 nums[0…i-1] 的和。 - 第二次遍历 (求解)： - 创建一个 std::unordered_map<int, int> memo。 - 遍历这个 prefixSum 数组（从 prefixSum[0] 到 prefixSum[n]）。 - 在 memo 中查找 prefixSum[j] - k，累加答案。 - 将 prefixSum[j] 存入 memo。 例如:

int subarraySum(std::vector<int>& nums, int k) {
    int n = nums.size();
    // 步骤 1: 预处理前缀和数组
    std::vector<int> prefixSum(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
    }

    // 步骤 2: 初始化哈希表
    std::unordered_map<int, int> memo;
    memo[0] = 1;  // 处理从索引 0 开始的子数组

    int total_count = 0;

    // 步骤 3: 遍历前缀和数组
    for (int j = 1; j <= n; ++j) {
        int needed = prefixSum[j] - k;

        // 查找左侧存在吗？
        if (memo.count(needed)) {
            total_count += memo[needed];
        }

        // 维护哈希表
        memo[prefixSum[j]]++;
    }

    return total_count;
}

常见题型包括: - 基础（一维）与二维前缀和 - 前缀和 + 哈希表：解决特定和（如和为 k）的子数组问题的经典组合。 - 距离和（绝对值问题） - 状态压缩前缀和（处理位运算或小状态集）

树上的前缀和

在树结构中，前缀和的概念可以通过路径和来实现。路径和是指从树的根节点到当前节点的所有节点值的累加和。例如LC 437. 路径总和 III.

题目: 给定一个二叉树的根节点 root 和一个整数目标和 targetSum ，求该树中 路径和等于目标和 的路径数量。路径 不需要从根节点开始，也不需要在叶子节点结束，但路径方向必须是向下的（只能从父节点到子节点）。

// 1. "前缀和账本" (哈希表)
// 存储 {前缀和 -> 该和出现的次数}
std::unordered_map<long long, int> prefixSumCount;

// 2. 最终答案
int totalPaths = 0;

// 3. 目标值
int target;

/**
 * @brief 深度优先搜索 (DFS) 辅助函数
 * @param node 当前节点
 * @param currentPathSum 从根节点到 *当前节点* 的路径总和
 */
void dfs(TreeNode* node, long long currentPathSum) {
    // Base Case: 节点为空，结束递归
    if (node == nullptr) {
        return;
    }

    // --- 1. 处理当前节点 ---

    // 更新当前路径的前缀和
    currentPathSum += node->val;

    // 查找 "补数" (currentPathSum - target)
    // 看看在祖先中，是否存在一个前缀和 `complement`
    long long complement = currentPathSum - target;
    
    // 如果 `complement` 存在于 "账本" 中，说明找到了路径
    if (prefixSumCount.count(complement)) {
        totalPaths += prefixSumCount[complement];
    }

    // --- 2. 更新状态并进入子树 ---

    // 将当前节点的前缀和加入 "账本"，供其子节点使用
    prefixSumCount[currentPathSum]++;

    // 递归处理左右子树
    dfs(node->left, currentPathSum);
    dfs(node->right, currentPathSum);

    // --- 3. 恢复现场 (回溯) ---

    // 离开当前节点，返回父节点时，必须将当前节点的前缀和从 "账本" 中移除
    // 这是为了防止干扰 "兄弟" 节点的计算
    prefixSumCount[currentPathSum]--;
}

int pathSum(TreeNode* root, int targetSum) {
    // 初始化目标值
    target = targetSum;
    
    // 初始化哈希表 "账本"
    // 放入 {0, 1} 是为了正确计算 "从根节点开始" 的路径
    prefixSumCount[0] = 1;
    
    // 启动 DFS，初始前缀和为 0
    dfs(root, 0);
    
    // 返回最终统计的路径总数
    return totalPaths;
}

前缀积

前缀积 (Prefix Product) 与前缀和类似，但用于计算数组元素的乘积。它在处理区间乘积查询时非常有用。 例如LC 238. 除自身以外数组的乘积: 给你一个整数数组 nums，返回一个数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。要求你在 O(n) 时间复杂度内完成此操作，且不使用除法。

std::vector<int> productExceptSelf(std::vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) return nums;

    // 结果数组 answer，同时也作为存储前缀积的辅助空间（O(1) 额外空间）
    std::vector<int> answer(n);
    
    // ----------------------------------------------------
    // 第一阶段：计算前缀积 (Prefix Product)
    // ----------------------------------------------------
    
    // 初始化：answer[i] 存储 nums[i] 左边所有元素的乘积。
    
    // 1. 初始化第一个元素
    // 解释：answer[0] 左边没有元素，乘积为 1。
    answer[0] = 1;
    
    // 2. 从左向右遍历，计算并存储前缀积
    for (int i = 1; i < n; ++i) {
        // 解释：answer[i] 等于 answer[i-1] 乘以 nums[i-1]
        // 即：P[i] = P[i-1] * nums[i-1]
        answer[i] = answer[i - 1] * nums[i - 1];
    }
    
    // 此时 answer 数组存储的是：[P[0], P[1], P[2], ..., P[n-1]]
    
    // ----------------------------------------------------
    // 第二阶段：计算后缀积 (Suffix Product) 并得到最终结果
    // ----------------------------------------------------
    
    // 初始化一个变量来实时存储后缀积
    // 解释：初始时，后缀积为 1，对应于数组右端元素的右侧。
    int suffix_product = 1; 

    // 3. 从右向左遍历，计算最终答案
    for (int i = n - 1; i >= 0; --i) {
        
        // 解释：最终答案 = (左边乘积 P[i]) * (右边乘积 S[i])
        // answer[i] 存储着 P[i]，suffix_product 存储着 S[i]。
        answer[i] = answer[i] * suffix_product;
        
        // 解释：更新 suffix_product，将 nums[i] 加入乘积链中，供 i-1 位置使用。
        // 即：S[i-1] = S[i] * nums[i]
        suffix_product *= nums[i];
    }
    
    return answer;
}

这道题利用了前缀积和后缀积的思想, 通过两次遍历数组, 分别计算出每个位置左边和右边的乘积保存下来, 从而实现了在一次遍历的过程中还可以O(1)时间复杂度查询内得到每个位置的结果.

在遍历的过程中实现O(1)时间复杂度查询是个很常见的技巧, 关键在于预先计算并存储所需的信息（如前缀积和后缀积, 以及哈希表等），使得每次查询时不需要重复计算。

差分数组

差分数组 (Difference Array) 一般用于高效区间更新。 - 原理：通过维护一个差分数组 diff，使得每次区间更新操作都降为 O(1) 时间。 - 效果：之后可以通过一次前缀和计算，得到最终的数组状态。

给你一个数组 nums，我们定义它的差分数组 diff 如下： - diff[0] = nums[0] - diff[i] = nums[i] - nums[i-1] (对于 i > 0) - 惊人的特性：从 diff 数组还原 nums 数组，只需要对 diff 求前缀和即可。 -

关键操作：如果我们要对 nums 的区间 [i, j]（闭区间）上的所有元素都加上 val： - nums[i] 增加了 val，而 nums[i-1] 不变，所以 diff[i]（即 nums[i] - nums[i-1]）增加了 val。 - nums[i+1] 到 nums[j] 这一段，由于 nums[k] 和 nums[k-1] 都增加了 val，它们的差 diff[k] 不变 - nums[j] 增加了 val，而 nums[j+1] 不变，所以 diff[j+1]（即 nums[j+1] - nums[j]）减少了 val。

结论：一次 O(n) 的区间更新 [i, j] 被转化为了两次 O(1) 的单点更新！ - diff[i] += val; if (j + 1 < n) { diff[j + 1] -= val; }

例题: LC 1109. 航班预订统计. 有 n 个航班，编号从 1 到 n。有一个预订表 bookings，其中 bookings[i] = [first, last, seats] 表示从 first 到 last 的航班都预订了 seats 个座位。请返回一个长度为 n 的数组 answer，其中 answer[i] 是第 i 个航班的总预订座位数。

std::vector<int> corpFlightBookings(std::vector<std::vector<int>>& bookings, int n) {
    
    // 步骤 1: 初始化差分数组
    // 我们使用 n 个元素，对应 0 到 n-1 下标
    // diff[i] 对应第 i+1 号航班
    std::vector<int> diff(n, 0);

    // 步骤 2: 处理所有更新 (O(1) / query)
    for (const auto& booking : bookings) {
        // 题目编号从 1 开始，数组下标从 0 开始
        int first = booking[0];
        int last = booking[1];
        int seats = booking[2];
        
        // 转换为 0-based 下标
        int i = first - 1; 
        int j = last - 1;

        // 应用差分
        // 1. 在区间的起始点 i 加上 val
        diff[i] += seats;

        // 2. 在区间的结束点 j 的下一个位置 j+1 减去 val
        // 注意检查边界
        if (j + 1 < n) {
            diff[j + 1] -= seats;
        }
    }

    // 步骤 3: 还原结果 (O(n))
    // 通过对差分数组求前缀和，来还原出最终的航班座位数
    // 还原后的数组可以直接用 diff 自身来存储
    for (int i = 1; i < n; ++i) {
        // 第 i 个航班的座位 = 第 i-1 个航班的座位 + 第 i 个航班的“变化量”
        diff[i] += diff[i - 1];
    }

    // 步骤 4: 返回
    // 此时 diff 数组已经变成了我们想要的 answer 数组
    return diff;
}

常见题型包括: - 一维差分：用于高效处理区间更新、单点查询的问题，常与扫描线思想结合。 - 二维差分：用于处理子矩阵的批量更新。