前缀和与差分

Published: June 14, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 前缀和技术
• 高维前缀和
• 差分技术

前缀和技术

考虑这样一个问题，给定一个静态数组$a_1,\ldots,a_n$，之后回答$q$个请求，每个请求给出$l,r$，要求计算$\sum_{i=l}^ra_i$。

这种静态询问的问题，可以用前缀和技术来加速，具体做法就是我们维护另外一个序列$b_0,b_1,\ldots,b_n$，其中$b_0$为加法$0$，对于$i\geq 1$，有$b_i=\sum_{j=1}^ia_i=b_{i-1}+a_i$。很显然$b$序列我们可以$O(n)$时间复杂度内求出。之后对于任意询问$\sum_{i=l}^ra_i$，有$\sum_{i=l}^ra_i=b_r-b_{l-1}$。因此对于每个请求我们都可以$O(1)$求解。

当然如果给定序列$b$，我们也可以很容易还原$a$，因为$a_i=b_i-b_{i-1}$。

前缀和技术实际上有点类似于傅里叶变换，将元素转换到另外一个空间中进行求解，从而实现一些操作加速，而另外一些操作减速。这里加速的就是区间和，而减速的就是普通的赋值修改操作（每次修改和赋值的时间复杂度都变成了$O(n)$）。

高维前缀和

现在假设有$k$维矩形，记$f(i_1,\ldots,i_k)$为单元$(i_1,\ldots,i_k)$中的数值。同时记$g(i_1,\ldots,i_k)=\sum_{1\leq j_1\leq i_1, \ldots, 1\leq j_k\leq i_k}f(i_1,\ldots,i_k)$。

要算高维前缀和，我们可以定义$h(i_1,\ldots,i_k,t)=\sum_{1\leq j_t\leq i_t,\ldots,1\leq j_k\leq i_k}f(i_1,\ldots,i_{t-1},j_t,\ldots,j_k)$。于是乎$g(i_1,\ldots,i_k)=h(i_1,\ldots,i_k,0)$。

下面我们来推导$h$，可以发现有：

$$h(i_1,\ldots,i_k,t)=h(i_1,\ldots,i_t-1,\ldots,i_k,t)+h(i_1,\ldots,i_t,\ldots,i_k,t+1)$$

因此我们可以花总共$O(kS)$的时间复杂度和空间复杂度求解出结果，其中$S$是矩形的体积。

题目1：给定$n$个数值$a_1,\ldots,a_n$，其中$0\leq a_1,\ldots,a_n<10^6$。记$f(x,i)$表示数字$x$的十进制中最低的第$i$位的数值。记$g(x_1,\ldots,x_k)$表示一个数字$y$，其中$y$的十进制的第$i$位等于$\min_j f(x_j,i)$。现在要求对于每个数$0\leq x <10^6$，计算$g(x)=\sum_{S\subseteq {a_1,\ldots,a_n}\land f(S)=x}\sum_{s\in S}s$，将输出结果模某个素数。

首先我们可以将每个整数看成一个$6$维向量。很显然这道题要求我们计算高维前缀和，但是如何保证$f(S)=s$呢。我们可以用容斥解决这个问题，先求出$\sum_{S\subseteq {a_1,\ldots,a_n}\land f(S)\geq x}\sum_{s\in S}s$，其中$f(S)\geq x$表示$f(S)$的每个维度的数值都大于等于$x$在该维度的数值。这个很好算。

算出来后，我们用可以用容斥$O(2^6)$找出$g(x)$。

总的时间复杂度为$O((2^6+6)\cdot 10^6)$。

题目2：给定$n$个正整数$a_1,\ldots,a_n$，要求找到最大的一个正整数$x$，满足给出的正整数至少有一半能整除$x$。其中$1\leq n\leq 10^5$，且$1\leq a_i\leq 10^{18}$。

提供一道题目。

首先我们随机选择一个数$a_i$，$a_i$能整除$x$的概率至少为$\frac{1}{2}$。这意味着$x$很大概率是$a_i$的因子。

但是我们不能暴力枚举$a_i$的因子，因为$a_i$的因子可能有$O(10^5)$个。实际上我们需要遍历所有正整数，记遍历的正整数为$y$，那么将所有$gcd(a_i,y)$的因子的计数全部增加$1$。之后找最大的计数超过一半的$a_i$因子。

这个过程非常类似于高维前缀和，如果我们把$a_i$分解为素因子形式$a_i=p_1^{c_1}\ldots p_k^{c_k}$，我们用向量表示可以得到$(c_1,c_2,\ldots,c_k)$。这其实就是高维前缀和。根据文章中提到的方法，我们可以$O(10^5\times 15)$来计算高维前缀和，总的时间复杂度为$O(10^5(\log_210^{18}+15+\log_2n))$。

之后我们多随机几次，保证正确率即可。

差分技术

前缀和技术可以用于快速查询区间和但是不支持修改，而差分技术则允许我们快速进行区间更新但是不支持查询。二者是对立的。

考虑在一维数组上做差分，原数组为$a$，而差分得到的数组为$b$，满足$a_i=\sum_{j=1}^ib_j$。考虑如何支持区间$[l,r]$全部增加$v$，实际上考虑到$b$中的变化，可以发现$b_l$需要增加$v$，而$b_{r+1}$需要减少$v$。因此一次区间更新就变成了两次单点修改。如果我们要恢复$a$，则可以用前缀和技术计算$b$的前缀和即可。

二维数组的差分也类似，这里不多讲。

题目1：给定一个数组$a$，支持$n$次操作，每次在区间$[l,r]$中加上一个等差数列。要求输出最终的$a$。

这个问题非常简单，可以发现等差数列可以由仿射变换得到，即可以表示为$kx+b$的形式，其中$x$是元素的下标。我们可以把$k$和$b$分开来维护。这样问题变成了区间$k$增加一定值和$b$增加一定值，这就是普通的差分问题了。

题目2：给定一个长度为$n$的数组$a$，处理$m$次操作，每次选择一个区间$[l,r]$以及一个整数$d$，之后元素$i$加上$i-l+d\choose d$。要求输出最终的数组。其中$1\leq n,m\leq 10^5$，$0\leq d\leq 100$。答案模素数$p$。

提供一道题目。

首先我们可以认为数组初始值为$0$，只要在最后输出的时候加上$a_i$即可。

之后考虑一次修改的意义，我们可以考虑维护一个$(k+1)\times n$的网格$A$。我们先简单认为$r=n$始终成立。之后我们考虑从$(d,l)$出发，每次只能向下和向右移动。可以发现我们到$(0,i)$的方案数正好是$i-l+d\choose d$种方案。现在考虑多个请求，我们实际上可以合并到同一个网格中处理，可以发现这样结果并不会多统计。

现在我们考虑$r<n$的情况，这时候显然会导致$j>r$的列多统计了。我们考虑一个请求对于$(i,r+1)$的影响，此时单元格都多加了$r+1-l+(d-i)\choose d-i$，我们需要减去这个值。最简单的方案是我们在单元格上直接减去这些值，由于我们单元格最终是用来算前缀值的，因此减少$(i,r+1)$会对$(i-1,r+1)$也会产生影响，因此$(i,r+1)$单元格实际上要减去的值是$r-l+(d-i)\choose d-i$。

时间复杂度和空间复杂度均为$O(100(n+m))$。