前缀和

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

前缀和和区间修改

考虑这样一个问题,给定一个静态数组$a_1,\ldots,a_n$,之后给定$q$个请求,每个请求给出$l,r,x$,要求对所有$l\leq i\leq r$,将$a_i$变成$a_i+x$。在处理完所有请求后,输出$a_1,\ldots,a_n$。

我们也可以对应的用前缀和实现区间修改操作。不妨令$a_1=\ldots=a_n=0$(如果不是,最后加回到结果就可以了)。具体做法就是维护一个修改序列$b_0,\ldots,b_n$,我们保证真实的结果为$a_i=\sum_{j\geq i}b_i$。因此对于修改$l,r,x$,我们只需要将$b_r$增加$x$,同时将$b_{l-1}$减少$x$。因此每个请求我们都可以$O(1)$求解。最后我们用公式可以直接$O(n)$还原出$a$。

高维前缀和

现在假设有$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)$。