前缀和算法

给定n个整数a1，a2，……，an，求它们两两相乘再相加的和，即 S = a1⋅a2 + a1⋅a3 + ⋯ + a1⋅an + a2⋅a3 + ⋯ + an−2⋅an−1 + an−2⋅an + an−1⋅an

我们可以将S改写成这种形式：

而对于（2+3+4+5+6+7）、（3+4+5+6+7）、......（6+7）、（7)如果采取

for(int i=0;i<n;i++)

        for(int j=i+1;j<n;j++)

方式，如果n非常大，显然花费时间很长。我们采用前缀和方法可以快速计算

前缀和数组的每一项元素是原数组的前n项和

#include <stdio.h>
int num[1000010]; //数组
long long prenum[1000010];//前缀和数组
int main()
{
	int n, x;
	long long sum = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &num[i]);
		if (i == 0) prenum[i] = num[i];
		prenum[i] = prenum[i - 1] + num[i];
	}
	for (int i = 0; i < n; i++) {
		sum += num[i] * (prenum[n - 1] - prenum[i]);
	}
	printf("%lld", sum);
	return 0;
}