算法基础-前缀和、差分、离散化

前缀和、差分、离散化

参考资料：

前缀和 & 差分 - OI Wiki

离散化 - OI Wiki

前缀和

数列前 \(n\) 项的和，是一种重要的预处理方式。

一维前缀和

可得到其递推式\(S_0=0,S_i = S_{i-1}+a_i\)

作一维前缀和数组 \(ps\)，其中下标i表示前 \(i\) 项的和

对区间[l,r]求和，显然用 \(ps[r]-ps[l-1]\) 即可，时间复杂度为 \(O(1)\)

二维/多维前缀和

将一维前缀和扩展到多维的情形。其常见的求解方法有两种

基于容斥原理

多用于二维前缀和的情形。给定大小为 \(m\times n\) 的二维数组 \(A\) ，要求求出其前缀和 \(S\)。那么，\(S\) 同样是大小为 \(m\times n\) 的二维数组，且

\[S_{i,j} = \sum\limits_{i'\leq{i} }\sum\limits_{j'\leq{j}}A_{i'j'}\]

显然，对于 \(S_{i,j}\)，我们可以通过容斥原理获得:

\[S_{i,j} = A_{i,j}+S_{i-1,j}+S_{i,j-1}-S_{i-1.j-1}\]

形象的说，当前元素的值为上面的值和左边的值相加，减去左对角线的值后再加上原数组的对应下标的值。

当然，对于第一行和第一列，其值代表原数组第一行和第一列的前缀和

逐维前缀和

对于一般的情形，给定 \(k\) 维数组 \(A\)，大小为 \(N\)，同样要求得其前缀和 \(S\)。

\[S_{i...i_k} = \sum\limits_{i'_1\leq{i_1} }...\sum\limits_{i'_k\leq{i_k}}A_{i'...i'_k}\]

从上式可以看出，\(k\) 维前缀和就等于 \(k\) 次求和。那么，每次只考虑一个维度，固定所有其它维度，然后求若干个一维前缀和，这样对所有 \(k\) 个维度分别求前缀和后，就得到 \(k\) 维前缀和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//三维前缀和示例
int N1, N2, N3;
std::vector<std::vector<std::vector<int>>> a,
    ps;  // (N1 + 1) x (N2 + 1) x (N3 + 1).

// Calculate prefix sum of 3d array.
void prefix_sum() {
  ps = a;

  // Prefix-sum for 3rd dimension.
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i][j][k - 1];

  // Prefix-sum for 2nd dimension.
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i][j - 1][k];

  // Prefix-sum for 1st dimension.
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i - 1][j][k];
}

因为考虑每一个维度时，都只遍历了整个数组一遍，这样的时间复杂度是 \(O(kN)\)的

基于此，我们可以实现对一定范围的区域求区域和。例如，对二维原矩阵中，求左上顶点为 \((i_1,j_1)\) 、右下顶点 \((i_2,j_2)\) 的矩形区域和，可通过如下式子求解

\[S[i_2][j_2]-S[i_1-1][j_2]-S[i_2][j_1-1]+S_[i_1-1][j_1-1]\]

特例：子集和DP

维度比较大的情形，经常出现在一类叫做 子集和（sum over subsets,SOS）的问题中。这是高维前缀和的特例。

问题描述如下。考虑 大小为 \(n\) 的集合的全体子集上面定义的函数 \(f\)，现在要求求出其子集和函数 \(g\) ，它满足

\[g(s)=\sum\limits_{T\subseteq{S}}f(T)\]

即 \(g(s)\) 等于其所有子集 \(T\sube S\) 上的函数值 \(f(T)\) 的和。

首先，子集和问题可以写成高维前缀和的形式。注意到，\(S\) 的子集可以通过状态压缩的思想表示为 \(n\) 维数组，且每个维度下标都一定在 \(\set{0,1}\) 中。同时，子集的包含关系就等价于下标的大小关系，即

\[T\sube{S}\Longleftrightarrow \forall{i}(t_i\leq s_i)\]

所以，对子集求和，就是求这个 \(n\) 维数组的前缀和。

显然，通过逐维前缀和的方法可求得子集和，时间复杂度为 \(O(n2^n)\)

子集和的逆操作需要通过容斥原理进行。子集和问题也是快速莫比乌斯变换的必要步骤之一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//参考代码
int n;
vector<int> a,ps; //length = 1<<n(2^n)
void sum_of_subset(){
    ps = a;
    for(int i=0;i<n;i++){
        //每次得到第i维的累加和
        for(int st=0;st<(1<<n);st++){
            if(st >> i & 1){ //二进制的st的第i位为1
                //ps[...1...] += ps[...0...] (i-th dimension)
                ps[st] += ps[st^(1<<i)]; //按字符串维度进行n维前缀和
            }
        }
    }
}

树上前缀和

一维前缀和还可以推广到有根树（树根为1）的情形。通过预处理前缀和，可以快速求解树上一段路径的权值和。

点权的情形

首先讨论权值存储在结点处的情形。设结点 \(x\) 处有权值 \(a_x\) 。可通过递推关系

\[S_1=a_1, S_x =S_{fa(x)}+ a_x\]

求出从根结点到结点 \(x\) 的路径上的结点的权值和，其中， \(fa(x)\) 表示 \(x\) 的父结点。预处理万前缀和后，就可以通过

\[S_x+S_y-S_{lca(x,y)}-S_{fa(lca(x,y)}\]

或

\[S_x+S_y-2*S_{fa(lca(x,y))}-a_{lca(x,y)}\]

计算连接结点 \(x\) 和 \(y\) 的路径上的结点权值和。\(lca(x,y)\) 表示结点 \(x\) 与 \(y\) 的最近公共祖先。

边权的情形

该情形几乎可以转化为点权的情形。对于所有非根结点，记 \(edge(x)\) 为连接结点 \(x\) 和其父结点 \(fa(x)\) 的边，结点 \(x\) 处存储的是边 \(edge(x)\) 上的边权。根结点处存储的权值是 \(0\) 。那么，显然递推关系和点权一致。

\[S_1 = 0, S_x = S_fa(x)+edge(x)\]

注意，查询结点 \(x\) 与 \(y\) 的路径和时，和点权略有不同：

\[S_x+S_y-2*S_{lca(x,y)}\]

因为实际上是边上的值，路径上的边并未重复，只有最近公共祖先到根节点的路径和是冗余的。

子树和

和数组的情形不同，由于树的首位不对称，所以自下而上（从树叶到树根）和自上而下（从树根到树叶），求前缀和得到的结果并不相同。一般树上前缀和指的是自上而下的前缀和。而另一种做法，实际上是得到结点子树的总和，本文称作 子树和。

以点权为例，显然有

\[T_x = \sum\limits_{y\in desc(x)}a_z\]

其中, \(desc(x)\) 表示 \(x\) 自身和其所有子孙结点的集合

与树上前缀和不同，子树和并不能应用于 \(O(1)\) 求路径权值和，但是它可以用于理解下文的树上差分。

差分

​ 与前缀和相对，是前缀和的逆运算。相较于给定某一序列求它的差分，竞赛中更为常见的情景是，通过维护差分序列的信息，实现多次区间修改。在区间修改结束后，可以通过前缀和恢复原序列的信息，实现对原序列的查询。注意修改操作一定要在查询操作之前。

一维差分

为避免顺序冲突，从最末项往前开始构造差分

\[D_i = a_i-a_{i-1},a_0=0\]

性质

​ 差分的前缀和就是原数列，基于此可推出其与原数列前缀和的关系

\[S_i=\sum\limits_{j=1}^i\sum\limits_{k=1}^jD_k=\sum\limits_{j=1}^i(i-j+1)D_j\]

​ 差分信息常常用于维护多次对序列的一个区间加上一个数，并在之后一次或多次询问序列某一位的取值。

​ 假设要将序列 \({a_i}\) 在区间 \([l,r]\) 中的每个数加上一个 \(v\) 。可以做如下操作：

\[D_l=D_l+v,\ D_{r+1}=D_{r+1}-v \]

​ 单次修改是 \(O(1)\) 的，查询需要做一次 \(O(n)\) 的前缀和操作，随后的查询都是 \(O(1)\) 的复杂度。

二维/多维差分

​ 差分同样可以推广到多维的情形。将多维差分看作多维前缀和的逆运算，那么，求多维差分数组的操作就相当于根据多维前缀和求它的原数组。

​ 可以利用容斥原理，例如二维差分可用：

\[D_{i,j} = a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1}\]

​ 但是，如果要计算整个差分数组，更为简单高效的做法是逐维差分，即穷举所有维度，沿着每个维度都计算一遍数组的差分。

​ 二维差分信息常用于维护二维数组的多次矩形加。例如，对左上角 \((x_1,y_1)\) 、右下角 \((x_2,y_2)\) 的矩阵中每个数字都加上 \(v\) ，可做：

  • \(D_{x_1,y_1}\) += \(v\)
  • \(D_{x_1,y_2+1}\) -= \(v\)
  • \(D_{x_1+1,y_2}\) -= \(v\)
  • \(D_{x_1+1,y_2+1}\) += \(v\)

​ 在所有修改操作结束后，只需要执行一遍二维前缀和，就可以快速查询更新后的数组的值。

​ 注意，尽管修改操作适用于多维，但单次修改操作需要 \(O(2^k)\) ，随着 \(k\) 增大而不再实用

树上差分

差分可推广到有根树的情形，用于实现树上一段路径的区间加操作。根据维护的信息存储在结点上还是边上，树上差分可以分为 点差分 与 边差分，它们在实现上会稍有不同。另外，相对于树上前缀和操作，更常用的是在所有修改操作后做子树和再查询。本节讨论的就是这种情形。

点差分

如果要对结点 \(x\) 和 \(y\) 之间的路径上的所有点权都加 \(v\)，可以对它的差分序列 \({D_x}\) 做如下操作：

  • $D_x $ += \(v\)
  • \(D_{lca(x,y)}\)-= \(v\)
  • $D_y $ += \(v\)
  • \(D_{fa(lca(x,y))}\) -= \(v\)

在所有修改操作完成后，可以计算一次子树和，就能得到更新后的点权。

边差分

如果要对结点 \(x\) 和 \(y\) 之间的路径上的所有边权都加 \(v\) ，可以对它的差分序列 \({D_x}\) 做如下操作:

  • \(D_x\) += \(v\)
  • \(D_y\) += \(v\)
  • \(D_{lca(x,y)}\) -= \(2v\)

STL上的前缀和与差分

有时，元素个数足够，但是需要做差分或前缀和的并非元素下标，而是元素值，此时数组长度往往不够用。那么可以利用STL里的数据结构来存放，比如 map 类型。

例题

3347. 执行操作后元素的最高频率 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxFrequency(vector<int>& nums, int k, int numOperations) {
    map<int,int> mp;
    unordered_map<int,int> cnt;
    for(auto i:nums){
        cnt[i]++;
        mp[i]; //本身元素要参与
        mp[i-k]++;
        mp[i+k+1]--;
    }
    int ans = 0;
    int sum = 0;
    for(auto t=mp.begin();t!=mp.end();t++){
        int i = t->first;
        sum += mp[i];
        ans = max(ans,min(sum,numOperations+cnt[i]));
    }
    return ans;
}

离散化

离散化是一种数据处理的技巧，本质上可以看成是一种 哈希，其保证数据在哈希以后仍然保持原来的 全序/偏序 关系。

通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便的处理，而最终影响结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照排名来处理问题，即离散化。

用来离散化的可以是大整数、浮点数、字符串等等。

实现

将一个数组离散化，并进行查询是比较常用的应用场景。

方法一

通常原数组中会有重复的元素，一般把相同的元素离散化为相同的数据。

方法如下：

  1. 创建原数组的副本
  2. 将副本中的值从小到大排序
  3. 将排序好的副本去重
  4. 查找原数组的每一个元素在副本中的位置，位置即为排名，将其作为离散化后的值。
1
2
3
4
5
6
7
8
//arr[i]为初始数组
for(int i=1;i<=n;i++)
    tmp[i = arr[i];
sort(tmp+1,tmp+n+1);
int len = unique(tmp+1,tmp+n+1)-(tmp+1); //去重
for(int i=1;i<=n;i++){
    arr[i] = lower_bound(tmp+1,tmp+len+1,arr[i])-tmp.begin(); //给出排名并赋值
}

方法二

根据题目要求，有时候会把相同的元素根据输入顺序离散化为不同的数据。

显然靠 lower_bound() 函数实现就有些困难了，需要换一种思路：

  1. 创建原数组的副本，同时记录每个元素出现的位置。
  2. 将副本按值从小到大排序，当值相同时，按出现顺序从小到大排序。
  3. 将离散化后的数字放回原数组
1
2
3
4
5
6
7
8
9
10
struct Data{
    int idx,val;
    bool operator<(const Data& o) const{
        if(val == o.val) return idx<o.idx;
        return val < o.val;
    }
}tmp[MAXN]; //pair亦可
for(int i=1;i<=n;++i) tmp[i] = Data{i,arr[i]};
sort(tmp+1,tmp+n+1);
for(int i=1;i<=n;++i) arr[tmp[i].idx] = i;

复杂度

对于方法一，去重复杂度为 \(O(n)\) ，排序复杂度为 \(O(nlogn)\)，最后的 \(n\) 次查找复杂度为 \(O(nlogn)\) 。

对于方法二，排序复杂度为 \(O(nlogn)\)。

故两种方法的时间复杂度均为 \(O(nlogn)\) ，空间复杂度为 \(O(n)\) 。