__ 前缀和不应该是一个算法,它应该说是一个思维,水到渠成的思维,或许它是遍布最广的算法~

算法1:(一维)它的思想好像跟它的算法一样简单

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int N = 100010;

int a[N],sum[N];
int n,m,l,r;

int main()
{
    cin >> n >> m;

    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i];
        sum[i] = sum[i-1] + a[i];
    }

    while(m--)
    {
        cin >> l >> r;

        cout << sum[r] - sum[l-1] << endl;
    }
    return 0;
}

算法2:(二维矩阵)
我表达能力一直都不太行,但是在写这个代码的时候我想到了数电老师的说的一句话:

计算机喜欢机械的重复性的内容,繁不繁不重要,这点跟人不同,人嵌套几次就不太行了

很多算法都有这种思想,比如图论,DP;

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1010;

int a[N][N],sum[N][N];
int n,m,q;


void  solve()
{
    int x1, y1 ,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    cout << sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] << endl;
}

int main()
{
    cin >> n >> m >> q;

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            cin >> a[i][j];

    for(int i = 1 ; i <= n ; i++)//计算机喜欢重复的指令程序哦!!!
        for(int j = 1 ; j <= m ; j++)
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j];

    while(q--)
    {
        solve();
    }

    return 0;
}

例题一:壁画
没什么好说的,直接秒了,这道题应该是”简单”

#include <iostream>
#include <algorithm>
#include  <cstring>
#include <cmath>

using namespace std;

const int  N = 5e6 + 7;

char str[N];
int sum[N];

int main()
{
    int t; cin >> t;
    int n;

    for(int m = 1 ; m <= t ; m++)
    {
        cin >> n;//长度

        cin >> (str+1);

        for(int i = 1 ; i <= n ; i++) sum[i] = sum[i-1] + str[i] - '0';

        int ans = 0,num;
        if(n & 1)//奇数
        {
            int cnt = n/2 + 1;
            for(int i = 1,j = cnt; j <= n ; i++,j++)
            {
                num = sum[j] - sum[i-1];
                ans = max(ans,num);
            }
            cout << "Case #" << m << ": " << ans << endl;
        }

        else//偶数
        {
            int cnt = n/2;
            for(int i = 1,j = cnt; j <= n ; i++,j++)
            {
                num = sum[j] - sum[i-1];
                ans = max(ans,num);
            }
            printf("Case #%d: %d\n",m,ans);
            //cout << "Case #" << m << ": " << ans << endl;
        }
    }
    return 0;
}