1. 高精度

高精度加法

• 大整数的存储：用数组存，但是是逆过来存，个位放在数组第一位，十位为第二位，以此类推，类似小端法，因为涉及进位，用这种存储法方便在数组末端添加数，若类似大端存储的话不方便进位。
• 模拟加法，每位相加再加上上一位的进位就好了。

模板：

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;                                             //进位
    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) C.push_back(t);
    return C;
}

高精度减法

• 模拟减法，按位相减，若不够减则向上借一位，此位加10

模板：

// C = A - B, 满足A >= B, A >= 0, B >= 0若不满足则算B-A再加个负号就好了
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();
    return C;
}

高精度乘法

• 一般为大数乘小数
• 模拟乘法，大数每一位分别乘小数，该位的结果应为乘法的结果%10再加上进位，进位为乘法的结果/10

模板：

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

高精度除法

• 大数除小数
• 模拟除法其实是按位来的，大数的最高位除小数，余数*10加上下一位继续除，直到除完，就有结果和余数了
  模板：

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    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());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

2. 前缀和

• 什么是前缀和？
  哈哈，其实是级数，是和函数S_n
  就是给了一个数组（按数列理解）a₁……a_n前缀和S_i=a₁+……+a_i， S₀=0
  （前面从1开始定义就是为了有S₀=0，也才能有后面的那个求一段数的和（可以少写判断））
• 求前缀和: S_i=S_i-1+a_i
• 作用：能快速的求出数组里面一段数的和

核心：

一维前缀和：

• S[i] = a[1] + a[2] + ... a[i]
• a[l] + ... + a[r] = S[r] - S[l - 1]

二维前缀和：

• S[i, j] = 第i行j列格子左上部分所有元素的和
• 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
• S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

3. 差分

• 什么是差分（前缀和的逆运算）
  就是给了一个数组a₁……a_n
  构造：b₁……b_n
  使得数组a是数组b的前缀和
  数组b就是数组a的差分
  即：a_i=b₁+……+b_i
  也就是：
  b₁=a₁
  b₂=a₂-a₁
  b₃=a₃-a₂
  ……
  b_n=a_n-a_n-1
  （构造不重要，因为可以看成是进行了n次插入值，就是假定最开始a全是0，然后每个加上了现在的值）
• 作用：

1. 有b数组了，通过O(n)的时间求前缀和就能得到a，
2. 给区间[l, r]中的每个a_i加上c，这个操作如果很多，如果暴力的话那每一遍都是O(n)了，但用差分就是O(1)

一维差分

• 插值操作：给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

二维差分

• 插值操作：给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
• S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c