Acwing算法学习之前缀和

2021-04-30 01:26

阅读：545

标签：names int 模板题 ons stream 直接 ble 理解 code

前缀和十分好理解，与数学上面的等差数列类同

先上前缀和模板

以下是一维前缀和

公式如下

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

二维前缀和模板

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

模板题

Acwing 795.前缀和
来源 : https://www.acwing.com/problem/content/797/
直接套模板，没有什么难点

#include 

using namespace std;

const int N = 100001 + 10;
int q[N], s[N], n, m;

int main()
{
    cin >> n >> m;
    for (int i = 1; i > q[i], s[i] = s[i - 1] + q[i];
    
    
    while (m -- )
    {
        int l, r;
        cin >> l >> r;
        
        cout

二维前缀和模板题

Acwing 796.子矩阵的和
来源： https://www.acwing.com/problem/content/798/

#include 

using namespace std;

const int N = 1000 + 10;
int a[N][N], s[N][N], n, m, k;

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i > a[i][j];
    for (int i = 1; i > x1 >> y1 >> x2 >> y2;
        
        cout

Acwing算法学习之前缀和

标签：names int 模板题 ons stream 直接 ble 理解 code

原文地址：https://www.cnblogs.com/qwer0553/p/13231351.html

上一篇：windows10 13个必学快捷键

下一篇：CentOS7下python3.x的源码安装

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Acwing算法学习之前缀和
文章链接：http://soscw.com/index.php/essay/80223.html

亲，登录后才可以留言！

Acwing算法学习之前缀和

前缀和十分好理解，与数学上面的等差数列类同

以下是一维前缀和

二维前缀和模板

模板题

二维前缀和模板题

评论

热门文章

推荐文章

最新文章

置顶文章