前缀和、差分、离散化与堆

zifuneko · 2024-04-14 18:31:48 · 算法·理论

\text{1 前缀和}

\text{1.1 前缀和的定义}

前缀和算法是一种常用的优化技术，用于加速某些涉及连续子数组或子序列求和的问题。它基于一个简单但强大的思想，通过提前计算并存储数组的前缀和，以便在后续查询中可以快速获取任意区间的和。

在许多算法问题中，我们需要频繁地查询子数组的和，例如最大子数组和、连续子数组的平均值等。传统的方法是在每次查询时遍历数组，并计算所需区间的和，这样会导致时间复杂度较高。

而前缀和算法通过预处理数组，计算出每个位置的前缀和，并将其保存在一个额外的数组中。这样，在查询时，我们只需要简单地减去两个前缀和即可得到所需子数组的和，从而将查询时间降低为 O(1) 的常数复杂度。

\text{1.2 使用前缀和的方法}

前缀和算法是一种用于高效计算数组前缀和的算法。前缀和是指数组中某个位置之前（包括该位置）所有元素的和。

前缀和算法的基本思想是通过一次遍历数组，计算每个位置的前缀和，并将其存储在一个新的数组中。然后，可以通过查询新数组中的元素，快速计算出任意子数组的和。

具体步骤如下：

1. 创建一个新的数组 q ，长度与原数组相同。
2. 初始化 q[1] 为原数组的第一个元素。
3. 从原数组的第二个元素开始，依次计算 q[i] = q[i-1] + a[i] ，其中 a 为原数组。
4. 完成后， q 数组中的每个元素即为对应位置之前所有元素的和。

通过前缀和算法，可以在 O(1) 的时间复杂度内计算出任意子数组的和。例如，要计算原数组中从位置i到位置j的子数组和，只需计算 q[j] - q[i-1] 即可。如果 i 为 0 ，则直接返回 q[j]。

如上，如果要求原数组中 a 的第 2 至第 5 项时，q[5] - q[1] 即是答案。

特别的，在建立时需要把第 0 项空出，因为在计算 q[i-1] 可能会越界（如果不特判），为了使 a[i,j] = q[j] - q[i-1] 具有普遍性，在建立时需要把第 0 项空出。

前缀和算法在解决一些与子数组和相关的问题时非常有用，例如求解子数组和等于目标值的个数、求解最大子数组和、求解最长连续子数组和等。

\text{1.3 二维前缀和}

二维前缀和的建立：

\text{2 差分}

模板题：\text{P2367} 语文成绩

\text{2.1 差分的定义}

差分其实就是前缀和的逆运算。

对于一个数组 a ，差分数组 c 的定义是：

对差分数组做前缀和可以还原为原数组。

\text{2.2 使用差分的方法}

利用差分数组可以实现快速的区间修改。

如何将区间 [l,r] 都加上 x 呢？

如上图，当我们将原数组 a 中的区间 [2,5] 都加上 2，不难看出，在差分数组中只有下标 2 与 6 的位置发生了变化。

所以说，在差分数组中将区间 [l,r] 都加上 x ，只需要在差分数组中将 c[l] 的位置增加 x ，将 c[r+1] 的位置减少 x 即可。

c[l] += x;
c[r+1] -= x;

但是注意：差分数组不能实现“边修改边查询（区间和）”，只能实现“多次修改完成后多次查询”，因为查分查询的时间复杂度为 O(n) （因为要使用前缀和变换为原数组）。如果要实现“边修改边查询”的功能，则需要使用树状数组、线段树等数据结构，增删查的时间复杂度均为 O(\log n) 。

\text{3 离散化}

其法有三：

2. 排序，去重，二分；
3. 哈希（散列表）.

排序、去重的常用方法：

sort(a+1, a+n+1);
int n_copy = n;
n = unique(a+1, a+n+1)-a-1;

\text{4 堆}

• 堆是一种完全二叉树。
• 堆要求孩子节点要小于等于父亲节点（大顶堆）

\text{R155852805} 记录详情