XCPC历险记第二章！带你玩转高精度、前缀和与差分！-创新互联

前缀和是一个数组中前i项的和，记作Si。若一个数组为：a1，a2，a3，a4，……那么Si = a1 + a2 + a3 + …… + ai。

观察可知，Si = S(i-1) + ai。（记S0 = 0，便于处理边界)。

前缀和可以用来计算数组中一段数据的和。例如要求数组中【l，r】区间的和，我们可以用Sr - S(l - 1)。
接下来让我们看看具体的代码实现吧！

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

二维前缀和是一个矩阵某点左上角全部元素（包括该点）的和。例如有某个m*n矩阵A，那么（i，j）点的前缀和S（i，j）= a（1,1）+a（1,2）+……+a（1，j）+……+a（i，j）。在解决前缀和相关问题时，我们不妨把“和”看作“面积”，这样会直观一些。

二维前缀和可以用来计算矩阵某一个区域内所有数据的和。例如：

那么从（i1，j1）到（i2，j2）的所有数据的和为：
S = S（i2，j2）- S（i1，j2 - 1）- S（i2，j1 - 1）+ S（i1 - 1，j1 - 1）（因为左上角的小区域被减了两次，所以要加回来）

观察图可知，S（i，j）= S（i - 1，j）+ S（i，j-1）- S（i-1，j-1）（因为被加了两次，所以要减掉）+ a（i，j）。
有了上面的了解，我们就可以来看看代码模板了。

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

差分是前缀和的逆运算。设已经有一个数组a1，a2，a3，a4……，这个数组的差分是指这样一个数组：它的前缀和为原数组。那么我们很容易就可以构造出差分数组：b1 = a1，b2 = a2 - a1，b3 = a3 - a2，b4 = a4 - a3……但实际上这个构造并不重要，只要我们观念上知道有一个构造即可。
差分的方法在什么时候有用呢？比如说我们要执行这样的操作：把a数组中【l ，r】内的数全部加上某个常数c，如果运用差分，把查分数组中的bl + c，b（r+1） -   c，那么由于b是a的差分数组，【l，r】内的数就自动全加上c了。而对于数组a，我们可以这样看：它初始的时候所有值为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;
}

矩阵a（ij）的差分矩阵是指这样的矩阵：a（ij）中的项是差分矩阵前缀和。那么借助一维差分和二维前缀和的经验，我们知道可以这样初始化差分矩阵b（假若要把阴影部分加上c）（这里我们不必考虑b的具体构造）：

那么b应该作相应的变化：b（x1,y1）+= c，b（x2+1，y1）-= c，b（x1，y1+1）-= c ，b（x2+1，y2+1）+= c。为什么这样修改以后a中阴影部分会+c呢？、因为对于a数组，靠近往右往下方向是相加的b数组中的项增大的方向，那么我们只要给区域左上角的b（x1，y1）加上c，那么x1，y1以后的a中的项（即右下角的项）都会加上c。然后在阴影之外我们不希望a中数据有变化，所以只要做相应的调整即可。

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

好啦！以上便是本篇文章的全部内容。这里的代码均出自Acwing闫学灿大佬之手，这是他的主页：
Acwing闫学灿
博主给代码加上了注释和自己的思考总结。祝大家学习愉快！

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章题目：XCPC历险记第二章！带你玩转高精度、前缀和与差分！-创新互联
链接分享：https://www.cdcxhl.com/article34/ioose.html

成都网站建设公司_创新互联，为您提供微信小程序、建站公司、网站内链、动态网站、搜索引擎优化、外贸网站建设

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联