前缀和与差分

Published: by Creative Commons Licence

  • 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))$。