一二维前缀和及差分（算法描述）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了一二维前缀和及差分（算法描述），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含903字，纯文字阅读大概需要2分钟。

内容图文

基本描述：

一维：

前缀和：结合数组前n项和理解

    sn[0]=an[0];
    for(int i=1;i<longth;i++)//初始化
        sn[i]=an[i]+sn[i-1];

差分：

多次给定[l,r],标记l和r范围

令an[l]+k

　an[r+]-r

多次操作后，利用辅助数组sn求an的前缀和即可得到标记的数组

二维：

前缀和：结合面积理解

 

#include <iostream>
using namespace std;
int an[10][10],sum[10][10]={0};
int main ()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)//输入
        for(int j=1;j<=m;j++)
            cin>>an[i][j];
    for(int i=1;i<=n;i++)//初始化
        for(int j=1;j<=m;j++)//为避免j-1，i-1越界，不使用最外边那一行，令其初始化为0：
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+an[i][j];//粉红色框定的面积等于红色框定的面积+绿色框定的面积-蓝色框定的面积+粉红的所处的点对应小框面积
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
            cout<<sum[i][j]<<' ';
            cout<<endl;
        }

    return 0;
}

 

差分:

标记：an[左上]+=k;an[右下+1]+=k;an[右上+1]-=k;an[左下+1]-=k;达到标记的目的；

 主要用处：

前缀和：多次询问区间和，

差分：标记一维区间或者二维区间

内容总结

以上是互联网集市为您收集整理的一二维前缀和及差分（算法描述）全部内容，希望文章能够帮你解决一二维前缀和及差分（算法描述）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---