Ericnth的小站

  • 前缀和
  • 一维
  • 二维
  • 差分
  • 一维
  • 二维
  • 你可能还想了解...
  • 首页
  • 编程学习笔记
  • 系统与软件
  • 摄影
  • 随笔
  • 论坛
  • 公告

前缀和与差分学习笔记

  • Zhang, Xuheng
  • 2021-02-03
  • 0

其实是复习笔记。


前缀和

一般用来求区间和。

一维

  • 现在给出一个数列 $a$,要求回答 $m$ 次询问,每次询问下标 $l$ 到 $r$ 的和。

算好前缀和,
```s[r]−s[l−1]``` 就是答案。

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005],s[1005];
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    s[1] = a[1];
    for(int i=2; i<=n; i++) s[i] = s[i-1] + a[i]; 
    int l,r;
    cin>>l>>r;
    cout<<s[r] - s[l-1]<<endl;
    return 0;
}

二维


差分

一维

差分数组的功能是修改区间,查询点。修改 $O(1)$,查询 $O(n)$。

  • 给定一个长度为 $n$ 的数列 $a$,有 $q$ 个操作,每次操作给定 $l,r,x$ 表示 $[l,r]$ 区间所有的数都加上 $x$。并求修改后的序列a。

预处理:

c[1]=a[1];
for(int i=2;i<=n;i++)
    c[i]=a[i]-a[i-1];

修改:

void update(int l,int r,int x) {
    c[l] += x;
    c[r+1] -= x;
}

查询:

int sum(int x) {
    int ans = 0;
    for(int i=1;i<=x;i++)
        ans += c[i];
    return ans;
}
  • U69096 前缀和的逆

差分。

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005],s[1005];
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    s[1] = a[1];
    for(int i=2; i<=n; i++) s[i] = a[i] - a[i-1];
    for(int i=1; i<=n; i++) printf("%d ",s[i]);
    return 0;
}

二维

类比二维前缀和和一维差分,可以简单推测出二维差分的公式:

c[i][j] = a[i][j] − a[i−1][j] − a[i][j−1] + a[i−1][j−1]

你可能还想了解...

  • A Bayesian Analysis of High School Acceptance Rates in Shanghai
  • HYRing项目代码解读
  • 算法讲解之贪心算法(转)
  • 算法讲解之回溯法(转)
  • C/C++ IDE推荐
© 2023 Ericnth的小站
Theme by Wing
沪ICP备2020025694号 沪公网安备31011202012861号
  • {{ item.name }}
  • {{ item.name }}