一 高精度计算

  int能表示范围为2^32，这看起来很大，但在大数据时代的如今，不说是int 哪怕是long long也是不够的，那么为了使用或计算这些超出或远超整形大小的数，我们这些数的计算方法称为高精度计算。

（1)高精度加法（A+B，A和B均为高精度）

  我们采用的方法是开两个数组A，B，然后用这两个数组来模拟两个大数之间的加法运算。代码实现要注意两个细节：
  ①实现过程中一定要保证A的长度大于B
  ②实现过程中注意数的存储顺序是从低位向高位，具体过程如下所示：

  代码如下所示：

vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;//t用于表示进位
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t!=0) C.push_back(t);//用于保存进位
    return C;
}

（2）高精度减法（满足A>B)

  思路和高精度加法基本一致，只是模拟的过程是减法而不是加法

vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 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;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    //去掉首位的所有0
    return C;
}

二 前缀和与差分

（1）前缀和（一种预处理方法，可降低时间复杂度）

  前缀和是一种重要的预处理，能大大降低查询的时间复杂度。前缀和是以求和的方式灵活地面对区间询问。例如以下问题：
  给你一串长度为 n 的数列 a1, a2, a3, …, an，再给出 m 个询问，每次询问给出 L, R 两个数，要求给出区间 [L, R] 里的数的和。如果使用前缀和处理以后很容易可以得到
则 上 述 题 目 的 结 果 为 S [ L ] − S [ R − 1 ] 则上述题目的结果为S[L]-S[R-1] 则上述题目的结果为S[L]−S[R−1]
  时间复杂度显然降低

  ①一维前缀和（用于处理一维数组）

表 达 式 为 S [ n ] = a 1 + a 2 + a 3 + . . . . a n 预 处 理 递 推 公 式 为 ： S [ n ] = S [ n − 1 ] + a n 表达式为S[n]=a_1+a_2+a_3+....a_n\\预处理递推公式为：S[n]=S[n-1]+a_n 表达式为S[n]=a1​+a2​+a3​+....an​预处理递推公式为：S[n]=S[n−1]+an​
  ②二维前缀和（用于处理二维数组）
  二维前缀和的公式如下
二 维 前 缀 和 表 达 式 为 ： S [ x , y ] = ∑ i = 1 x ∑ i = 0 y a i j 预 处 理 递 推 公 式 为 ： S [ x , y ] = S [ x − 1 , y ] + S [ x , y − 1 ] − S [ x − 1 , y − 1 ] + a x y 二维前缀和表达式为：S[x,y]=\sum_{i=1}^x\sum_{i=0}^ya_{ij}\\预处理递推公式为：\\S[x,y]=S[x-1,y]+S[x,y-1]-S[x-1,y-1]+a_{xy} 二维前缀和表达式为：S[x,y]=i=1∑x​i=0∑y​aij​预处理递推公式为：S[x,y]=S[x−1,y]+S[x,y−1]−S[x−1,y−1]+axy​
  这个公式可以根据以下方法记忆：

  代码实现思路如下：
  （1）初始化所有的S[n][0],S[0][m]（第一行与第一列）
  （2）根据递推公式推出所有的S[x][y]