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），那么

#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的表达式），那么其实是一种递推！

#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;
}

#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;
            
}

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;
}

#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;
}