前缀和与差分学习笔记

其实是复习笔记。


前缀和

一般用来求区间和。

一维

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

算好前缀和,
“`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;
}

差分。

#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]
版权声明:本文为博主Zhang, Xuheng原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接: https://nth.ink/cpp/P2933.html

(广告由我们的赞助商提供,内容与本站无关)
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇