adjacent_difference（差分算法）
差分与前缀和相对，可以视为前缀和的逆运算。差分它可以维护多次对序列的一个区间修改一个数。差分就是用下一个元素减去当前元素，然后得到差值。第1个元素始终不变。
利用差分后再做前缀和可以得到原数列的性质，可以通过改变差分后的数组从而改变原数组。
template<class InputIterator,class OutputIterator>
OutputIterator adjacent_difference(InputIterator first,InputIterator end,OutputIterator result);
template<class InputIterator,class OutputIterator,class op>
OutputIterator adjacent_difference(InputIterator first,InputIterator end,OutputIterator result,op binary_op);#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<numeric>
int main()
{
//原数组
vector<int> v{ 0,1,5,9,10,2,7,1 };
for (auto c : v)
{
cout << c <<" ";
}
cout << endl;
//对原数组做差分保存到result数组中
vector<int> result(v.size());
adjacent_difference(v.begin(), v.end(),result.begin());
for (auto c : result)
{
cout << c << " ";
}
cout << endl;
//对result数组做前缀和，保存到数组v2中
vector<int> v2;
int tmp = 0;
for (auto c : result)
{
tmp += c;
v2.push_back(tmp);
}
for (auto c : v2)
{
cout << c << " ";
}
cout << endl;
//输出结果如下，对一个数组做差分后在做前缀和得到原数组
//0 1 5 9 10 2 7 1
//0 1 4 4 1 -8 5 -6
//0 1 5 9 10 2 7 1
return 0;
}inner_product（内积）
返回作为两个序列乘积而生成的元素的总和。步调一致地检查两个序列,将来自两个序列的元素相乘,将相乘的结果求和。由 init 指定和的初值。假定从beg2 开始的第二个序列具有至少与第一个序列一样多的元素,忽略第二个序列中超出第一个序列长度的任何元素。
template<class InputIterator1,class InputIterator2,class T>
T inner_product(InputIterator1 beg1,InputIterator1 end1,InputIterator2 beg2,T init);
template<class InputIterator1,class InputIterator2,class T,class op1,class op2>
T inner_product(InputIterator1 beg1, InputIterator1 end1, InputIterator2 beg2,T init,op1 BinOp1,op2 BinOp2)#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include <numeric>
int main()
{
vector<int> v{ 1,2,3,4 }, v2{ 1,2,3,4,5 };
int64_t res = inner_product(v.begin(), v.end(),v2.begin(), int64_t(0));
cout << res << endl;
//上述代码等于 res = 1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 0;
return 0;
}partial_sum（部分求和，前缀和）
template<class InputIterator,class OutputIterator>
OutputIterator partial_sum(InputIterator first,InputIterator last,OuputIterator result);
template<class InputIterator,class OutputIterator,class op>
OutputIterator partial_sum(InputIterator first,InputIterator end,OutputIterator result,op binary_op);#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include <numeric>
int main()
{
vector<int> v = { 1,2,3,4,5 }, v2(v.size());
partial_sum(v.begin(), v.end(), v2.begin());
for (auto c : v2)
{
cout << c << endl;
}
//对于1,2,3,4,5的序列产生1,1+2,1+2+3,1+2+3+4,1+2+3+4+5的序列保存在v2中
//对相同一个序列求差分和前缀都是相同的结果
vector<int> v = { 1,2,3,4,5,6,7,8 };
adjacent_difference(v.begin(), v.end(), v.begin());
partial_sum(v.begin(), v.end(), v.begin());
for (auto c : v)
{
cout << c << endl;
}
return 0;
}iota（名称容易和itoa和atoi搞混，这两个是字符串与数字转换函数）
这个函数用来设定某个区间的内容，使得每一个元素从指定的value值开始，呈现递增状态。
vector<int> v(10);
iota(v.begin(),v.end(),0);
// v中的内容是下面
// 0 1 2 3 4 5 6 7 8 9
Comments NOTHING