前缀和¶
约 97 个字 18 行代码 预计阅读时间 1 分钟
对前缀求和，两个前缀和之差就是区间和。更进一步，任何满足“大区间信息减小区间信息等于互补小区间信息”性质的运算，都可以类似前缀和的加速
presum_i=\sum\limits_{j=1}^i a_j
\sum\limits_{i=l}^r a_i =presum_r-presum_{l-1}
二维前缀和¶
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
s[i][j]=s[i][j-1]+a[i][j];
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
s[i][j]=s[i-1][j]+s[i][j];
高维前缀和¶
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
for(int k=1;k<=n;++k)
s[i][j][k]=s[i][j][k-1]+a[i][j][k];
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
for(int k=1;k<=n;++k)
s[i][j][k]=s[i][j-1][k]+a[i][j][k];
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
for(int k=1;k<=n;++k)
s[i][j][k]=s[i-1][j][k]+a[i][j][k];