前缀积与后缀积

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

• 引入
• 一、什么是前缀积和后缀积
• 二、如何使用前缀积后缀积
• • 1.思路
  • 2.前缀积后缀积的计算
  • 3.完整代码（C++）
  • 前缀和与后缀和
• 其他例题
• • 1.求数组中连续一段和，使其绝对值最小
  • 2.把一个数组从中间p位置分开，使得a[0]+…+a[p-1]与a[p]+a[p+1]+…+a[n-1]差值最小

通过一道例题引入前缀积和后缀积的用法

Description:
给出数列A1,A2,…,AN，并设
Bi = (A1 * A2 * A3 … AN) / Ai mod (10⁹ + 7)
现要求把所有的Bi 算出来

Input:
输入包含多组测试数据。对于每组数据，第1 行，1 个整数N(1 ≤N≤100,000), 表示数列的长度。第2行，N 个整数A1,A2,…,AN(1 ≤Ai≤109)，表示给出的数列。输入以一个 0 表示结尾。

Output:
对于每组数据，输出一行，N 个整数用空格分隔，表示算出的B1,B2,…,BN。

Sample Input:
3
1 2 3
0

Sample Output:
6 3 2

题目给的数据很大，如果一直乘下去，肯定会发生算术溢出。因此我们需要利用用取余的分配律 ：

(a*b)%c = (a%c * b%c)%c

这道题当然可以通过暴力求解。但如果要求你不用除法，并且在常数时间内得到题解呢？
那就要用到我们所说的前缀积和后缀积了。

对于给定的数组A[1…n] ：

• 前缀积：新建一数组B，数组中每一项B[i]保存A中[1…i]的积；即数组A前 i 项的积。
• 后缀积：新建一数组B，数组中每一项B[i]保存A中[i…n]的积；即数组A后 n-i 项的积。

对于上述例题，在无法使用除法的情况下，我们需要将思路转换一下：
 想要得到 Bi = (A1 * A2 * A3 … AN) / Ai mod (10⁹ + 7) 的值，除了求出数组A中所有数的积并且分别取模之后再除以Ai以外，我们还可以将Bi看做两个区块：即A[1…i-1]和A[i+1…n]的乘积对(10⁹ + 7)取模。
 也就是A数组中前i-1个数的前缀积 pre[i-1] 乘以 A数组中第i+1到n个数的后缀积 suff[i+1] 的结果取模后的值。

Bi = (pre[i-1]*suff[i+1]) % 1000000007

 已知数组A和其大小n之后，由前缀积和后缀积的概念可得：
前缀积：

	pre[0] = 1 ;
	for( int i=1 ; i<=n ; i++ )
        pre[i] = ( pre[i-1]*a[i] ) % 1000000007 ;

后缀积：

	suff[n+1] = 1 ;
	for( int i=n ; i>=1 ; i-- )
        suff[i] = ( suff[i+1]*a[i] ) % 1000000007 ;

#include 

#define MOD 1000000007
#define maxn 100002 ;

int main()
{
    int n ;
    int pre[maxn] , suff[maxn] ;
    int a[maxn] ;

    for( int i=1 ; i<=n ; i++ )
        scanf( "%d" , &a[i] ) ;

    pre[0] = suff[n+1] = 1 ;

    for( int i=1 ; i<=n ; i++ )
        pre[i] = ( pre[i-1]*a[i] ) % MOD ;  // pre[i]为数列a中前i个数的乘积

    for( int i=n ; i>=1 ; i-- )
        suff[i] = ( suff[i+1]*a[i] ) % MOD ;    // suff[i]为数组中后n-i个数的乘积

    for( int i=1 ; i<=n ; i++ )
        printf( "%d%c" , (pre[i-1]*suff[i+1])%MOD , (i==n)?'n':' ' ) ;
            // pre[i-1]*suff[i+1]为a数组除去a[i]之后，其余成员的乘积 

    return 0 ;
}

 与前缀积后缀积思路类似：

• 前缀和：新建一数组B，数组中每一项B[i]保存A中[0…i]的和；
• 后缀和：新建一数组B，数组中每一项B[i]保存A中[i…n-1]的和；

思路：
前缀和的性质：a[i]+a[i+1]+…+a[j]=sum[j]-sum[i-1]
将前缀和排序，取最小的两个

思路：
差值 = | p-1的前缀和-p的后缀和 | ；
记录p从0至n-1扫过时，最小的差值即为题解。

参考文章：
前缀积和后缀积-deqip44248
前缀和、前缀积-webcandy