刷题日记—前缀和

1.基本前缀和与差分思想
2.前缀和的拓展——前缀乘法—左右区间乘积的前后累乘。

点击查看代码

```cpp
#include <iostream>
#include<vector>
using namespace std;
//这道题实际上是前缀和的拓展，前缀乘法，根据题目要求可知，要求除当前元素以外的所有元素的乘积，实际上就是左乘积*右乘积，把左右乘积分别存储到数组里就可以
int main()
{vector<int> nums;int n;cin>>n;vector<int> left(n);vector<int> right(n);for(int i=0;i<n;++i){int x;cin>>x;nums.push_back(x);}left[0]=1;for(int i=1;i<n;++i){left[i]=left[i-1]*nums[i-1];}right[n-1]=1;for(int i=n-2;i>=0;--i){right[i]=right[i+1]*nums[i+1];}for(int i=0;i<n;++i){nums[i]=left[i]*right[i];cout<<nums[i]<<" ";}return 0;
}

</details>  
利用左右数组分别存储左右乘积，应当注意的是left(right)[i]=left(right)[i-1]*nums[i-1],并且left[0]=1,right[n-1]=1。