XCPC历险记第二章！带你玩转高精度、前缀和与差分！-创新互联
- 一、高精度剖析与例题讲解
- 1.A+B(A,B位数很大，如1e6级别）
- 2.A-B(A,B位数很大，如1e6级别）
- 3.A*b(A的位数很大，如1e6级别；但b相较A很小，如b的值在1e6级别）
- 4.A/b(A的位数很大，如1e6级别；但b相较A很小，如b的值在1e6级别
- 二、前缀和、差分剖析与例题讲解
- 二、1.前缀和
- 二、1、1.前缀和的求法
- 二、1、2.前缀和的作用
- 二、2.二维前缀和
- 二、2.1二维前缀和的作用
- 二、2.1前缀和的求法
- 二、3.差分
- 二、4.二维差分
高精度问题是一类处理长度（位数）很长的正整数的运算问题（以下均讨论非负数）。在学习具体的问题之前，我们首先要学习超长整数是如何存储的。对于超长整数，用某种数据类型来存储其实是行不通的，我们会把它的每一位存到数组里。在存储时，数组的小下标存低位，大下标存高位。比如若把123456（当然它不是超长整数，我们只是举个例子）存到数组里，那么就是6 5 4 3 2 1。这样做是因为加减乘除可能涉及到进位，而在数组尾部进行数据的修改是比较容易的。注意：不要混淆位数和数值！比如说，若一个数的数值<=10，那么它的取值范围是0-10；若一个数的长度<=10，那么它的取值范围是0-9999999999。
高精度问题主要分为以下几类：
让我们先来回忆一下竖式加法的流程：
这里的ti(i = 0,1,2,3)表示进位，因此ti = 0或1。我们可以发现，Ci = (Ai + Bi + ti)%10。因此要实现超长整数相加，只需要把数组对应位置的数以及进位数加起来再模10，就可以得到新数字的每一位。 那么就让我们来看看代码如何实现吧！
#include#includeusing namespace std;
//传引用，防止多开空间
vectoradd(vector&A,vector&B)
{vectorC;
//保存进位
int t = 0;
for(int i = 0;iif(i//用字符串的形式读数，可以拿到每一位
string a,b;
//定义大小可变化的数组
vectorA,B;
cin>>a>>b;
//由于读进来的形式是字符，因此为了拿到那一位，我们要减去偏移量，即字符0的ASCII码值。
//此外，我们要把数据倒着读进数组。
for(int i = a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
for(int i = b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
vectorC = add(A,B);
//倒着打印
for(int i = C.size()-1;i>=0;i--) printf("%d",C[i]);
return 0;
} 一定要好好看注释哦，作者想说的都在注释里啦！如果你感觉阅读本段代码有困难，不妨先看看这个——[
C++vector快速入门
数据的存储方式同上。那么相减的算法思想是怎样的呢？我们通过竖式计算图来观察一下：
我们可以发现，与加法不同的是减法需要借位。假设上一位借该位t（t=0或1），那么
| >=0 不需要借位 那么直接减就可以 得到Ai - Bi - t | |
|---|---|
| Ai - Bi - t | |
| <0 那么需要借位，也就是+10，得到Ai -Bi - t + 10 |
#includeusing namespace std;
#include//判断是否有 A>=B
bool cmp(vector&A,vector&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;
}
//C = A - B
//这里已经保证A>=B了
vectorsub(vector&A,vector&B)
{vectorC;
//由于已经保证A>=B，所以A.size()>=B.size()
for(int i = 0,t = 0;i//t为0表示不借位，为1表示借位
//与上面的高精度加法不同的是，这里的t不方便更新，所以我们应该把t定义在循环里面，这样方便每次循环的时候更新重置！
t = A[i] - t;
//防止越界
if(i0，就应该赋t给C。那么把二者结合起来就是下面的写法：
C.push_back((t+10)%10);
if(t<0) t = 1;
else t = 0;
}
//若出现形如003这样的结果，把0去掉
while(C.size()>1&&C.back()==0) C.pop_back();
return C;
}
int main()
{string a,b;
cin>>a>>b;
vectorA,B,C;
for(int i = a.size()-1;i>=0;i--) A.push_back(a[i] - '0');
for(int i = b.size()-1;i>=0;i--) B.push_back(b[i] - '0');
if(cmp(A,B))
{C = sub(A,B);
for(int i = C.size()-1;i>=0;i--) printf("%d",C[i]);
}
else
{C = sub(B,A);
printf("-");
for(int i = C.size()-1;i>=0;i--) printf("%d",C[i]);
}
} 首先，我们应该明白人类是怎么计算乘法的~~举一个例子看看吧！
**由于高精度乘法要把a看作整体，所以这里的相乘步骤与我们熟悉的逐位相乘略有不同，但原理是一样的：
我们可以看出乘法和加法的进位规则是类似的，下面让我们用代码来实现它吧！
#includeusing namespace std;
#includevectormul(vector&A,int&b)
{vectorC;
int t = 0;
//如果这里不加||t（即t!=0），会把结果的最高位（也就是C数组的最后一个元素）弄丢！
//与加法不同的是，这里我们尝试把一个循环和一个判断（关于t的判断）放到一块了
for(int i = 0;iif(i1&&C.back()==0) C.pop_back();
return C;
}
int main()
{string a;
int b;
cin>>a>>b;
vectorA,C;
for(int i = a.size()-1;i>=0;i--) A.push_back(a[i] - '0');
C = mul(A,b);
for(int i = C.size()-1;i>=0;i--) printf("%d",C[i]);
return 0;
} 我们还是先看看人类是怎么计算除法的。
(以下ri表示余数，初始r0设定为0）
我们可以发现，C3 = A3/b，r1 = (A3 % b)*10+A2，C2 = r1/b，r2 = (r1%b)*10+A3，C3 = r2/b，r3 = (r2%b)*10+A4，C4 = r3/b。
那么如何用代码实现这一过程呢？
#includeusing namespace std;
#include#include
vectordiv(vector&A,int&b,int&r)
{vectorC;
//r为余数，初始值为0
r = 0;
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()
{string a;
int b;
cin>>a>>b;
vectorA;
for(int i = a.size()-1;i>=0;i--) A.push_back(a[i] - '0');
int r = 0;
vectorC;
C = div(A,b,r);
for(int i = C.size()-1;i>=0;i--) printf("%d",C[i]);
cout< 说明1：与加、减、乘不一样的是，除法的运算是从最高位开始的。那么按道理来说，我们并不需要把超长整数倒着存进数组里。但是一道题目中往往加减乘除混杂，为了统一，我们仍然采用倒着存进数组倒着打印的方式。而也正因为如此，div函数中i要从A.size-1开始，即倒着读。那么得到的C数组也要翻转。
说明2：通过前面四个例子的分析，我们可以注意到，对于某个变量k，若在循环中写成k = f(k)（这里f(k)是关于k的表达式），那么其实是一种递推！
前缀和是一个数组中前i项的和，记作Si。若一个数组为：a1，a2，a3，a4，……那么Si = a1 + a2 + a3 + …… + ai。
二、1、1.前缀和的求法观察可知，Si = S(i-1) + ai。（记S0 = 0，便于处理边界)。
二、1、2.前缀和的作用前缀和可以用来计算数组中一段数据的和。例如要求数组中【l，r】区间的和，我们可以用Sr - S(l - 1)。
接下来让我们看看具体的代码实现吧！
#includeusing namespace std;
const int N = 1e6+10;
int n,m;
int a[N],s[N];
int main()
{scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
s[0] = 0;
//这是迭代！这不是递归！
for(int i = 1;i<=n;i++) s[i] = s[i-1]+a[i];
while(m--)
{int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",s[r] - s[l-1]);
}
return 0;
} 二维前缀和是一个矩阵某点左上角全部元素（包括该点）的和。例如有某个m*n矩阵A，那么（i，j）点的前缀和S（i，j）= a（1,1）+a（1,2）+……+a（1，j）+……+a（i，j）。在解决前缀和相关问题时，我们不妨把“和”看作“面积”，这样会直观一些。
二、2.1二维前缀和的作用二维前缀和可以用来计算矩阵某一个区域内所有数据的和。例如：
那么从（i1，j1）到（i2，j2）的所有数据的和为：
S = S（i2，j2）- S（i1，j2 - 1）- S（i2，j1 - 1）+ S（i1 - 1，j1 - 1）（因为左上角的小区域被减了两次，所以要加回来）
观察图可知，S（i，j）= S（i - 1，j）+ S（i，j-1）- S（i-1，j-1）（因为被加了两次，所以要减掉）+ a（i，j）。
有了上面的了解，我们就可以来看看代码模板了。
#includeusing namespace std;
const int N = 1010;
int n,m,q;
int a[N][N],s[N][N];
int main()
{//注意：若不给数组初始化，默认全部元素为0
scanf("%d%d%d",&n,&m,&q);
//注意：这里要从i=1，j=1开始！因为a数组下标从1开始会更方便些
for(int i = 1;i<=n;i++)
for(int j = 1;j<=m;j++)
scanf("%d",&a[i][j]);
//注意：这里也要从i=1，j=1开始！这样i-1、j-1以后才能从零开始
//迭代求前缀和
for(int i = 1;i<=n;i++)
for(int j = 1;j<=m;j++)
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] +a[i][j];
//多组询问
while(q--)
{int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
//求子矩阵和
printf("%d\n",s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);
}
return 0;
} 差分是前缀和的逆运算。设已经有一个数组a1，a2，a3，a4……，这个数组的差分是指这样一个数组：它的前缀和为原数组。那么我们很容易就可以构造出差分数组：b1 = a1，b2 = a2 - a1，b3 = a3 - a2，b4 = a4 - a3……但实际上这个构造并不重要，只要我们观念上知道有一个构造即可。
差分的方法在什么时候有用呢？比如说我们要执行这样的操作：把a数组中【l ，r】内的数全部加上某个常数c，如果运用差分，把查分数组中的bl + c，b（r+1） - c，那么由于b是a的差分数组，【l，r】内的数就自动全加上c了。而对于数组a，我们可以这样看：它初始的时候所有值为0，然后我们赋值时每次插入。
接下来让我们看看例题和解答代码吧！
using namespace std;
const int N = 100010;
int n, m;
//b是差分数组
int a[N], b[N];
//让b[l] + c，b[r+1]-c
void insert(int l, int r, int c)
{b[l] += c;
b[r + 1] -= c;
}
int main()
{scanf("%d%d", &n, &m);
//a、b数组下标都从1开始即可，因为这里没有边界条件
for (int i = 1; i<= n; i ++ ) scanf("%d", &a[i]);
//构造差分数组。由于最开始a、b数组中的元素全为0，因此最开始的时候b就是a的差分数组。那么对于每个新生成的a【i】，b【i】应该有相应的偏移。而对于b的某一项先-a【i】，后一项+a【i+1】，恰好能满足前缀和。，
for (int i = 1; i<= n; i ++ ) insert(i, i, a[i]);
while (m -- )
{int l r, c;
scanf("%d%d%d", &l, &r, &c);
insert(l, r, c);
}
//更新b数组，使得b数组变成自己的前缀和数组
for (int i = 1; i<= n; i ++ ) b[i] += b[i - 1];
for (int i = 1; i<= n; i ++ ) printf("%d ", b[i]);
return 0;
}矩阵a（ij）的差分矩阵是指这样的矩阵：a（ij）中的项是差分矩阵前缀和。那么借助一维差分和二维前缀和的经验，我们知道可以这样初始化差分矩阵b（假若要把阴影部分加上c）（这里我们不必考虑b的具体构造）：
那么b应该作相应的变化：b（x1,y1）+= c，b（x2+1，y1）-= c，b（x1，y1+1）-= c ，b（x2+1，y2+1）+= c。为什么这样修改以后a中阴影部分会+c呢？、因为对于a数组，靠近往右往下方向是相加的b数组中的项增大的方向，那么我们只要给区域左上角的b（x1，y1）加上c，那么x1，y1以后的a中的项（即右下角的项）都会加上c。然后在阴影之外我们不希望a中数据有变化，所以只要做相应的调整即可。
#includeusing namespace std;
const int N = 1010;
int n, m, q;
//a是原数组，b是差分数组
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}
int main()
{scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i<= n; i ++ )
for (int j = 1; j<= m; j ++ )
scanf("%d", &a[i][j]);
for (int i = 1; i<= n; i ++ )
for (int j = 1; j<= m; j ++ )
insert(i, j, i, j, a[i][j]);
while (q -- )
{int x1, y1, x2, y2, c;
cin >>x1 >>y1 >>x2 >>y2 >>c;
insert(x1, y1, x2, y2, c);
}
for (int i = 1; i<= n; i ++ )
for (int j = 1; j<= m; j ++ )
//更新b，使得它作为自己的前缀和数组
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
for (int i = 1; i<= n; i ++ )
{for (int j = 1; j<= m; j ++ ) printf("%d ", b[i][j]);
printf("\n");
}
return 0;
} 好啦！以上便是本篇文章的全部内容。这里的代码均出自Acwing闫学灿大佬之手，这是他的主页：
Acwing闫学灿
博主给代码加上了注释和自己的思考总结。祝大家学习愉快！
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
文章题目：XCPC历险记第二章！带你玩转高精度、前缀和与差分！-创新互联
URL标题：http://hbruida.cn/article/ioose.html
