这是第二节课，单纯从高精度也就是大数运算的角度来说，我记得之前做课设时候的数字加密器，用Java做直接就有BigDecimal类，可以做大数运算，相对而言c/c++就没这么便利了。前缀和和差分我好像是闻所未闻，大概就是这么个情况。
高精度
一般来说，超大数字用的不多，long在平时场景处理数据时候已经够用了，但是一旦用到了，c/c++没有相关处理机制，就很难受。目前的处理思路是把数字按位塞进数组里，然后再设计算法进行运算。涉及的有两个大数相加、相减，大数和一个较小的数相乘，大数除以一个较小的数。
加法
先上模板：
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> add(vector<int> &A,vector<int> &B)
{
//判断一下两个数的长度，用长的加上短的
if(A.size() < B.size()) return add(B,A);
vector<int> C;
//进位的存储
int t = 0;
//A[i] + B[i] + t，和10取余是当前位，除以10得到的是进位
for(int i = 0;i < A.size();i++)
{
t += A[i];
//很明显若B短，之后就变成了A[i] + t
if(i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
//最后若t不为0，说明还有进位，要塞进去
if(t) C.push_back(t);
return C;
}
int main()
{
vector<int> A,B;
string a,b;
cin>>a>>b;
for(int i = a.size() - 1;i >= 0;i--)
{
A.push_back(a[i] - '0');
}
for(int j = b.size() - 1;j >= 0;j--)
{
B.push_back(b[j] - '0');
}
auto C = add(A,B);
for(int i = C.size() - 1;i >= 0;i--)
{
cout<<C[i];
}
return 0;
}
算法实现比较简单，记得最后判断t的值来确定最后还用不用进位，处理数据的部分也是要注意的点，要把高位放进下标大的位置，从平常来看就是把数字倒着放入数组里。
容器的使用相比数组的好处就是可以直接用size()成员函数来判断长度也不用担心数组固定大小带来的各种问题，string的元素减'0'可以变成数字倒是之前没见过的，之前用c做主要语言时候基本是用c_str()成员函数把string类型转成c类型的字符串（就是字符数组），然后再用atoi()函数转成数字，学到了。
减法
先上模板：
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool cmp(vector<int> &A,vector<int> &B)
{
//当两个数字不等长的时候，肯定是长的大
if(A.size() != B.size()) return A.size() > B.size();
//等长的时候，比较的时候，从高位开始比较，高位大的就大
for(int i = A.size() - 1;i >= 0;i--)
if(A[i] != B[i])
return A[i] > B[i];
return true;
}
void trimZero(vector<int> &A)
{
while (A.back() == 0 && A.size() > 1) A.pop_back();
}
//保证A的长度大于等于B的长度，且两个数字都不小于0
vector<int> sub(vector<int> &A,vector<int> &B)
{
vector<int> C;
int t = 0;
for(int i = 0;i < A.size();i++)
{
t = A[i] - t;
if(i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if(t < 0) t = 1;
else t = 0;
}
//当数字的是高位有0的时候，把0删掉
trimZero(C);
return C;
}
int main()
{
vector<int> A,B,C;
string a,b;
cin>>a>>b;
for(int i = a.size() - 1;i >= 0;i--)
{
A.push_back(a[i] - '0');
}
for(int j = b.size() - 1;j >= 0;j--)
{
B.push_back(b[j] - '0');
}
//如果数据合法那么去0这一步完全可以去掉
//trimZero(A), trimZero(B);
if(cmp(A,B))
{
C = sub(A,B);
}
else
{
C = sub(B,A);
cout<<"-";
}
for(int i = C.size() - 1;i >= 0;i--)
{
cout<<C[i];
}
return 0;
}
主要注意的问题是，对应位数相减，如果从最高位开始有0，那么就要把0去掉，不然输出结果就会很奇怪。模板解决的只有大的减小的，且两个数都非负的情况，如果是其他情况可以通过结合加法的模板来计算，像是负数-正数可以转化成-(正数+正数)，完全可以用加法模板来做。
做这个题的时候，我的模板还是没有背熟，竟然在main()函数处理数据的部分都能写错，导致出现了段错误，每次出现段错误都只能自己慢慢查找老半天，丢人了。
乘法
这里的乘法指的是大数乘以一个较小的数字，单纯来说
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> mul(vector<int> &A,int b)
{
vector<int> C;
int t = 0;
for(int i = 0;i < A.size();i++)
{
t += A[i] * b;
C.push_back(t % 10);
//进位
t / = 10;
}
//当t不为0，说明进行到最后还有进位，要直接放入
if(t) C.push_back(t);
//其实如果上一步执行了，这一步基本不会执行了，这一步是为了除去从高位开始出现的0的
while(C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
string a;
vector<int> A,B;
int b;
cin >>a>>b;
for(int i = a.size() - 1;i >= 0;i--)
{
A.push_back(a[i] - '0');
}
B = mul(A,b);
for(int i = B.size() - 1;i >= 0;i--)
{
cout<<B[i];
}
return 0;
}
整个算法不少内容都和前两个算法的思想差不多，可以参考。
除法
一个大数除以一个较小的数字：
//A / b = C ... r,A >= 0,b > 0
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> div(vector<int> &A,int b,int &r)
{
r = 0;
vector<int> C;
//除法的处理是从高位开始的所以要倒着处理
for(int i = A.size() - 1;i >= 0;i--)
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
//存放的顺序颠倒了，要反转一下
reverse(C.begin(),C.end());
//去掉高位可能存在的0
while(C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
vector<int> A,C;
string a;
int b;
cin>>a>>b;
for(int i = a.size() - 1;i >= 0;i--)
{
A.push_back(a[i] - '0');
}
//r用来存储余数
int r = 0;
C = div(A,b,r);
for(int i = C.size() - 1;i >= 0;i--)
{
printf("%d",C[i]);
}
printf("\n");
printf("%d",r);
return 0;
}
具体处理，main()的部分基本和乘法的差别不大，函数部分要注意的地方就是除法是从高位开始处理的，其他的问题不是太大。
前缀和
前缀和简单的来说就是一个数列的前n项和作为一个新的数列S来存储的话，举例：S[5]就是数列的前五个项的和，此处特殊定义S[0] = 0，前缀和可以处理一些数组中的连续的数字之和这类的问题，例如要求一个数列第3到第5个数字的和，可以用前缀和表示成S[5] - S[2],特殊地，可以用S[5] - S[0]解决第1个到第5个数字和的问题。
前缀和的实现可以用递归来做，基于S[i] = S[i - 1] + a[i]:
//计算前缀和
int calcS(vector<int> &A, unsigned int n)
{
if(n == 0) return 0;
else return calcS(A,n - 1) + A[n - 1];
}
递归做法在处理大量数据的时候总会遇见各种超时，空间不够的问题，这个只能改写成栈的方式解决。
差分
差分可以说是前缀和的逆运算，试想一下，假设一个数列A，可以获得一个前缀和数列B；反过来说，数列B的差分数列就是数列A。
差分数列A的特点就是B[i] = A[1] + … + A[i]，如果要构造的话，可以令A[1] = B[1],A[2] = B[2] - B[1],A[3] = B[3] - B[2]…但是实际应用中，构造差分数列并不重要，重要的是应用这个差分的性质来解题。
假定一种情况：对于数组B的从下标l到下标r的所有的数字都加上一个c，如果是通常暴力做法，遍历一遍数组然后挨个往上加，那么就是O(n)的时间复杂度。但是还有另外一种方法：假设数组B有一个差分数组A，那么差分数组的前n项和等于B对应下标n的元素，那么，对A[l]加上一个c，那么根据性质B[l]往后的每个数都加上了一个c，但是要使B[r + 1]开始的值不要再加c了，那么就要对A[r + 1]加上一个c来抵消掉之前加上的c带来的影响。这样只修改了两个数字，时间复杂度是O(1)。
以下是上面提出问题的代码实现：
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n,m;
int group[N],group2[N];//group2是group的差分数列
void insert(int l,int r,int c)
{
group2[l] += c;
group2[r + 1] -= c;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++)
scanf("%d",&group[i]);
//怎么构造出差分数列呢？
for(int i = 1;i <= n;i++)
insert(i,i,group[i]);
while(m--)
{
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
insert(l,r,c);
}
//计算一遍group2的前缀和
for(int i = 1;i <= n;i++)
group2[i] += group2[i - 1];
for(int i = 1;i <= n;i++)
printf("%d ",group2[i]);
return 0;
}
二重差分的操作类似，若要对B的子矩阵都加上一个c，实际上操作就是对差分矩阵A的对应子矩阵的四角元素进行操作，左上和右下是加，左下和右上是减。