数据结构-高维前缀和

前置知识

• 前缀和

思路

在《【数据结构】前缀和》里，我们知道了前缀和是个好东西。
如果说，一维的前缀和不够用了，怎么办？
天空一声巨响，高维前缀和闪亮登场
先从二维数组谈起。
给定一个二维数组 $a$，要对其求前缀和，假设现在要求 $s_{i,j}$，而在其前面的都已经求出，如图。
$$\begin{array}{cccc}{a}_{1,1}& \dots & \dots & a_{1,j}\\ ⋮& \ddots & & ⋮\\ ⋮& & a_{i-1,j-1}& a_{i-1,j}\\ a_{i,1}& \dots & a_{i,j-1}& a_{i,j}\end{array}$$
我们尝试 $s_{i,j}=s_{i-1,j}+s_{i,j-1}+a_{i,j}$
但是，结合上图，不难发现，$s_{i-1,j-1}$ 这一部分被加了两次，算重了。
考虑减去 $s_{i-1,j-1}$，得到递推式
$$s_{i,j}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_{i,j}$$
设 $l$ 为左边界，$r$ 为右边界，$h$ 为上边界，$t$ 为下边界
我们不难发现
$$\sum _{i=h}^t\sum _{i=l}^r{a}_{i,j}=s_{t,r}-s_{h-1,r}-s_{t,l-1}+s_{h-1,l-1}$$
其他维度也可以同理递推。

优化

所以我们得到了如下式子：
一维 $s_i=s_{i-1}+a_i$
二维 $s_{i,j}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_{i,j}$
三维 $s_{i,j,k}=s_{i-1,j,k}+s_{i,j-1,k}+s_{i,j,k-1}-s_{i-1,j-1,k}-s_{i-1,j,k-1}-s_{i,j-1,k-1}+s_{i-1,j-1,k-1}$
好长
所以我们就需要引入下一个方法了。
同样以二维前缀和为例。
$$\begin{array}{cccc}{a}_{1,1}& \dots & \dots & a_{1,j}\\ ⋮& \ddots & & ⋮\\ ⋮& & a_{i-1,j-1}& a_{i-1,j}\\ a_{i,1}& \dots & a_{i,j-1}& a_{i,j}\end{array}$$
先横着遍历，在每一行做一维前缀和。
再竖着遍历，在每一列做一维前缀和。
这样就可以得到高维前缀和了。（可以自己理解一下）

数据结构参数

设 $S$ 为高维数组大小

• 时间复杂度：$\Theta (S)$
• 空间复杂度：$\Theta (S)$

实现代码

• 基础版本

//以二维为例
for (int i=1;i<=n;i++)
    for (int i=1;i<=m;i++)
        cin>>a[i][j];
for (int i=1;i<=n;i++)
    for (int i=1;i<=m;i++)
        s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
for (int i=1;i<=q;i++){
    cin>>l>>r>>h>>t;
    cout<<s[t][r]-s[h-1][r]-s[t][l-1]+s[h-1][l-1]<<'\n';
}

• 优化版本

//以二维为例
for (int i=1;i<=n;i++)
    for (int i=1;i<=m;i++)
        cin>>a[i][j];
for (int i=1;i<=n;i++)
    for (int i=1;i<=m;i++)
        s[i][j]=s[i-1][j]+a[i][j];
for (int i=1;i<=n;i++)
    for (int i=1;i<=m;i++)
        s[i][j]=s[i][j]+s[i][j-1];
for (int i=1;i<=q;i++){
    cin>>l>>r>>h>>t;
    cout<<s[t][r]-s[h-1][r]-s[t][l-1]+s[h-1][l-1]<<'\n';
}

练习

• ARC100E Or Plus Max
• CF1208F Bits And Pieces