• 售前

  • 售后

热门帖子
入门百科

c++灵活实现前缀和与差分

[复制链接]
无将大车 显示全部楼层 发表于 2022-1-15 18:53:12 |阅读模式 打印 上一主题 下一主题
前缀和与差分

1.一维前缀和

注意
<ol> 前缀和下标要从1开始,因为边界S0要定义成0。
  作用:可以快速求出某个数组区间内的和。
[code]#includeusing namespace std;const int N = 1e5 + 10;int s[N],a[N];//全局变量默认为0int main(){    int m,n;    cin>>n>>m;    for(int i=1;i>a;    for(int i=1;i>l>>r;        coutm>>q;    for(int i=1;ia[j];    for(int i=1;i x1 >> y1 >> x2 >> y2;        coutm;    for(int i=1;i>a;        insert(i,i,a);//重点理解==》差分(上面提到的加值操作)    }        while(m--)    {        int l,r,c;        cin>>l>>r>>c;        insert(l,r,c);    }        for(int i=1;i=1;i--)        for(int j=m;j>=1;j--) a[j] = a[j] - a[i-1][j] - a[j-1] + a[i-1][j-1];//方法一求差分数组(只需要开一个数组)            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

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作