• 一、高精度剖析與例題講解
• • 1.A+B(A,B位數(shù)很大，如1e6級(jí)別）
  • 2.A-B(A,B位數(shù)很大，如1e6級(jí)別）
  • 3.A*b(A的位數(shù)很大，如1e6級(jí)別；但b相較A很小，如b的值在1e6級(jí)別）
  • 4.A/b(A的位數(shù)很大，如1e6級(jí)別；但b相較A很小，如b的值在1e6級(jí)別
• 二、前綴和、差分剖析與例題講解
• • 二、1.前綴和
  • • 二、1、1.前綴和的求法
    • 二、1、2.前綴和的作用
  • 二、2.二維前綴和
  • • 二、2.1二維前綴和的作用
    • 二、2.1前綴和的求法
  • 二、3.差分
  • • 二、4.二維差分

高精度問(wèn)題是一類處理長(zhǎng)度（位數(shù)）很長(zhǎng)的正整數(shù)的運(yùn)算問(wèn)題（以下均討論非負(fù)數(shù)）。在學(xué)習(xí)具體的問(wèn)題之前，我們首先要學(xué)習(xí)超長(zhǎng)整數(shù)是如何存儲(chǔ)的。對(duì)于超長(zhǎng)整數(shù)，用某種數(shù)據(jù)類型來(lái)存儲(chǔ)其實(shí)是行不通的，我們會(huì)把它的每一位存到數(shù)組里。在存儲(chǔ)時(shí)，數(shù)組的小下標(biāo)存低位，大下標(biāo)存高位。比如若把123456（當(dāng)然它不是超長(zhǎng)整數(shù)，我們只是舉個(gè)例子）存到數(shù)組里，那么就是6 5 4 3 2 1。這樣做是因?yàn)榧訙p乘除可能涉及到進(jìn)位，而在數(shù)組尾部進(jìn)行數(shù)據(jù)的修改是比較容易的。注意：不要混淆位數(shù)和數(shù)值！比如說(shuō)，若一個(gè)數(shù)的數(shù)值<=10，那么它的取值范圍是0-10；若一個(gè)數(shù)的長(zhǎng)度<=10，那么它的取值范圍是0-9999999999。
高精度問(wèn)題主要分為以下幾類：

讓我們先來(lái)回憶一下豎式加法的流程：

這里的ti(i = 0,1,2,3)表示進(jìn)位，因此ti = 0或1。我們可以發(fā)現(xiàn)，Ci = (Ai + Bi + ti)%10。因此要實(shí)現(xiàn)超長(zhǎng)整數(shù)相加，只需要把數(shù)組對(duì)應(yīng)位置的數(shù)以及進(jìn)位數(shù)加起來(lái)再模10，就可以得到新數(shù)字的每一位。 那么就讓我們來(lái)看看代碼如何實(shí)現(xiàn)吧！

#include#includeusing namespace std;
//傳引用，防止多開(kāi)空間
vectoradd(vector&A,vector&B)
{vectorC;
    //保存進(jìn)位
    int t = 0;
    for(int i = 0;iif(i//用字符串的形式讀數(shù)，可以拿到每一位
    string a,b;
    //定義大小可變化的數(shù)組
    vectorA,B;
    cin>>a>>b;
    //由于讀進(jìn)來(lái)的形式是字符，因此為了拿到那一位，我們要減去偏移量，即字符0的ASCII碼值。
    //此外，我們要把數(shù)據(jù)倒著讀進(jìn)數(shù)組。
    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;
}

一定要好好看注釋哦，作者想說(shuō)的都在注釋里啦！如果你感覺(jué)閱讀本段代碼有困難，不妨先看看這個(gè)——[
C++vector快速入門(mén)

數(shù)據(jù)的存儲(chǔ)方式同上。那么相減的算法思想是怎樣的呢？我們通過(guò)豎式計(jì)算圖來(lái)觀察一下：

我們可以發(fā)現(xiàn)，與加法不同的是減法需要借位。假設(shè)上一位借該位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
//這里已經(jīng)保證A>=B了
vectorsub(vector&A,vector&B)
{vectorC;
    //由于已經(jīng)保證A>=B，所以A.size()>=B.size()
    for(int i = 0,t = 0;i//t為0表示不借位，為1表示借位
        //與上面的高精度加法不同的是，這里的t不方便更新，所以我們應(yīng)該把t定義在循環(huán)里面，這樣方便每次循環(huán)的時(shí)候更新重置！
        t = A[i] - t;
        //防止越界
        if(i0，就應(yīng)該賦t給C。那么把二者結(jié)合起來(lái)就是下面的寫(xiě)法：
        C.push_back((t+10)%10);
        
        if(t<0) t = 1;
        else    t = 0;
    }
    //若出現(xiàn)形如003這樣的結(jié)果，把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]);
    }
    
    
}

首先，我們應(yīng)該明白人類是怎么計(jì)算乘法的~~舉一個(gè)例子看看吧！

**由于高精度乘法要把a(bǔ)看作整體，所以這里的相乘步驟與我們熟悉的逐位相乘略有不同，但原理是一樣的：

我們可以看出乘法和加法的進(jìn)位規(guī)則是類似的，下面讓我們用代碼來(lái)實(shí)現(xiàn)它吧！

#includeusing namespace std;
#includevectormul(vector&A,int&b)
{vectorC;
    int t = 0;
    //如果這里不加||t（即t!=0），會(huì)把結(jié)果的最高位（也就是C數(shù)組的最后一個(gè)元素）弄丟！
    //與加法不同的是，這里我們嘗試把一個(gè)循環(huán)和一個(gè)判斷（關(guān)于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;
}

我們還是先看看人類是怎么計(jì)算除法的。

(以下ri表示余數(shù)，初始r0設(shè)定為0）
我們可以發(fā)現(xiàn)，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。
那么如何用代碼實(shí)現(xiàn)這一過(guò)程呢？

#includeusing namespace std;
#include#include

vectordiv(vector&A,int&b,int&r)
{vectorC;
    //r為余數(shù)，初始值為0
    r = 0;
    for(int i = A.size()-1;i>=0;i--)
    {r = r*10+A[i];
        C.push_back(r/b);
        r%=b;
    }
    //翻轉(zhuǎn)數(shù)組
    reverse(C.begin(),C.end());
    //也要去掉前導(dǎo)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<

說(shuō)明1：與加、減、乘不一樣的是，除法的運(yùn)算是從最高位開(kāi)始的。那么按道理來(lái)說(shuō)，我們并不需要把超長(zhǎng)整數(shù)倒著存進(jìn)數(shù)組里。但是一道題目中往往加減乘除混雜，為了統(tǒng)一，我們?nèi)匀徊捎玫怪孢M(jìn)數(shù)組倒著打印的方式。而也正因?yàn)槿绱?，div函數(shù)中i要從A.size-1開(kāi)始，即倒著讀。那么得到的C數(shù)組也要翻轉(zhuǎn)。
說(shuō)明2：通過(guò)前面四個(gè)例子的分析，我們可以注意到，對(duì)于某個(gè)變量k，若在循環(huán)中寫(xiě)成k = f(k)（這里f(k)是關(guān)于k的表達(dá)式），那么其實(shí)是一種遞推！

#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()
{//注意：若不給數(shù)組初始化，默認(rèn)全部元素為0
    scanf("%d%d%d",&n,&m,&q);
    //注意：這里要從i=1，j=1開(kāi)始！因?yàn)閍數(shù)組下標(biāo)從1開(kāi)始會(huì)更方便些
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            scanf("%d",&a[i][j]);
    //注意：這里也要從i=1，j=1開(kāi)始！這樣i-1、j-1以后才能從零開(kāi)始
    //迭代求前綴和
    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];
    //多組詢問(wèn)
    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是差分?jǐn)?shù)組
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數(shù)組下標(biāo)都從1開(kāi)始即可，因?yàn)檫@里沒(méi)有邊界條件
    for (int i = 1; i<= n; i ++ ) scanf("%d", &a[i]);
    //構(gòu)造差分?jǐn)?shù)組。由于最開(kāi)始a、b數(shù)組中的元素全為0，因此最開(kāi)始的時(shí)候b就是a的差分?jǐn)?shù)組。那么對(duì)于每個(gè)新生成的a【i】，b【i】應(yīng)該有相應(yīng)的偏移。而對(duì)于b的某一項(xiàng)先-a【i】，后一項(xiàng)+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數(shù)組，使得b數(shù)組變成自己的前綴和數(shù)組
    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是原數(shù)組，b是差分?jǐn)?shù)組
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，使得它作為自己的前綴和數(shù)組
            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;
}