前缀和

前缀和

一、介绍

前缀,顾名思义就是一个东西前面的点缀...(bushi

其实打比方来说就是:假如有一字符串ABCD,那么他的前缀就是A、AB、ABC、ABCD这四个从新从第一个字母一次往后开始拼接的字符串。当然这是字符串。但前缀和一般应用于数组,对于给定的数组a=[1,2,3,4],他的前 i 项和sum[i]就表示数组中a[0]~a[i]的和,具体为:
sum[0]=a[0]
sum[1]=a[0]+a[1]
......
sum[i]=sum[0]+sum[1]+...+sum[i];

二、定义

定义:前缀和是指某一序列的前 n 项和

基于前缀和的使用,我们一般把前缀和分为一维前缀和二维前缀和

三、一维前缀和

定义

基于一维数组的前缀和就是原数组前n个元素的和

const int N = 10010;
 
int a[N]; //原数组a[]
int s[N]; //前缀和数组s[]
 
//根据定义 一维前缀和s[i]
s[i] = a[1] + a[2] + a[3] +...+ a[i];
 
//举例 设i=3 根据上式可得
s[3] = a[1] + a[2] + a[3];
 
//根据上面举例,可以再一步写成
s[i] = s[i-1] + a[i]; 

需要注意的一点是:数组的下标都是从 1 开始的!!!

作用

主要作用是可以在O(1)时间情况下快速的求出任一区间[l,r]内的元素之和。

//例如求a[3]+...+a[10]之间的和,我们可以利用前缀和迅速求出:
  a[3]+...+a[10]
= (a[1]+a[2]+a[3]...+a[10]) - (a[1]+a[2])
= s[10] - s[2]
 
//根据上面举例,我们可以推导出求某一区间[l,r]内的和的公式
  a[l]+a[l+1]+...+a[r-1]+a[r] 
= s[r] - s[l-1];

方法

一维数组求前缀和方法

int a[100],s[100];
for(int i = 1; i<= 99; i++)
{
    scanf("%d",&a[i]);
}
for(int i = 1; i<= 99; i++)
{
    s[i] = s[i-1]+a[i];
}

实战演练!!!

「模板」前缀和

输入n个数,给出m个询问,询问区间[x,y]的和。

输入
  • 第一行为n和m,1<=n,m<=100000

  • 接下来一行为n个数,范围在0~100000之间

  • 接下来m行,每行两个数x,y,输出第x个数到第y个数之间所有数的和。保证x<=y

输出

m个输出

样例输入
5 3
1 2 0 7 6
1 3
2 2
4 5
样例输出
3
2
13
代码:
#include <bits/stdc++.h>
using namespace std;
int n,m;
long long a[100010],b[100010];//见注释1
int main()
{
	cin >> n >> m;
	for(int i=1; i<=n;i++)
	{
		cin >> a[i];
	}
	b[0]=0;
	for(int i=1;i<=n;i++)
	{
		b[i]=b[i-1]+a[i];
	}
	while(m--)
	{
		int l,r;
		cin >> l >> r;
		cout << b[r] - b[l-1] << "\n";
	}
	return 0;
}

注释①:测试范围大image

四、二维前缀和

定义

基于二维数组的前缀和,它是指一个前 i 行和前 j 列的子矩阵的和

const int N =100010;
int a[N][N] //原二维数组
int s[N][N] //二维前缀和数组
 
//根据定义可得
s[i][j] = a[1][1] + a[1][2] + ... + a[1][j]+
          a[2][1] + 1[2][2] + ... + 1[2][j]+
          a[3][1] +   ...   + ... + a[3][j]+
             +                         +
            ....                      ....
             +                         + 
          a[i][1] +   ...   + ... + a[i][j]

作用

主要作用是可以在是可以在O(1)情况下求出任何子矩阵的和

图解:

image

在这个矩阵(二维数组)中,我们要求上图中紫色区域的和,现在我们已经预处理出了所有点的前缀和,现在给定两个点\((x1,y1)\)\((x2,y2)\),我们需要求的是以这两个点连线为对角线的一个子矩阵的数值之和。首先我们可以把\(s[x2][y2]\)求出来,它代表整个大矩形的前缀和,然后我们分别减去它右边多出来的一块的前缀和和上边多出来一块的前缀和,但是需要注意下边的左上角被减了两次,所以我们需要加回来一次。故对于一次的查询是\(s[i][j]\)应该等于\(s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]\)

  • 所求子矩阵和=\(s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]\);

方法

二维数组求前缀和方法

const int N = 10010;
int a[N][N],s[N][N]
//n,m为键盘输入
for(int i = 1; i <= n; i++)
{
    for(int j = 1;j <= m; j++)
    {
       scanf("%d",&a[i][j]);
    }
}
for(int i = 1; i<= n; i++)
{
    for(int j = 1; j <= m; j++)
    {
       s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
    }
}

具体代码!!!

#include <iostream>
 
const int N = 1010;
int n,m,q;
int a[N][N],s[N][N];
 
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1;j <= m; j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for(int i = 1; i<= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
        }
    }
    while(q--)
    {
        int x1,y1,x2,y2,re;
        scanf("%d%d%d%d",&x1,&y2,&x2,&y2);
        re = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
        printf("%d\n",re);
    }
}

原文链接:https://www.cnblogs.com/momotrace/p/Prefix-sum.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:前缀和 - Python技术站

(0)
上一篇 2023年5月2日
下一篇 2023年5月3日

相关文章

  • 第四部分:Spdlog日志库的核心组件分析-logger

    Spdlog是一个快速且可扩展的C++日志库,它支持多线程和异步日志记录。在本文中,我们将分析Spdlog日志库的核心代码,探究其实现原理和代码结构。 Spdlog的基本架构 上一篇文章介绍了spdlog的五个主要组件,其中最重要是Logger、Sink和Formatter其中,Logger负责日志的记录和管理,Sink负责将日志输出到不同的目标(比如控制台…

    C++ 2023年4月18日
    00
  • 最少步数

    在各种棋中,棋子的走法总是一定的,如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性,因此,他规定马既能按“日”走,也能如象一样走“田”字。他的同桌平时喜欢下围棋,知道这件事后觉得很有趣,就想试一试,在一个(100*100)的围棋盘上任选两点A、B,A点放上黑子,B点放上白子,代表两匹马。棋子可以按“日”字走,也可以按“田”字走,俩人一…

    C++ 2023年4月25日
    00
  • 2023团队天梯模拟赛 L2-3 智能护理中心统计 and L3-1 塔防游戏(23分)

    L2-3 智能护理中心统计 智能护理中心系统将辖下的护理点分属若干个大区,例如华东区、华北区等;每个大区又分若干个省来进行管理;省又分市,等等。我们将所有这些有管理或护理功能的单位称为“管理结点”。现在已知每位老人由唯一的一个管理结点负责,每个管理结点属于唯一的上级管理结点管辖。你需要实现一个功能,来统计任何一个管理结点所负责照看的老人的数量。 注意这是一个…

    C++ 2023年4月19日
    00
  • C++ 并发编程实战 第二章 线程管控

    第二章 线程管控 std::thread 简介 构造和析构函数 /// 默认构造 /// 创建一个线程,什么也不做 thread() noexcept; /// 带参构造 /// 创建一个线程,以 A 为参数执行 F 函数 template <class Fn, class… Args> explicit thread(Fn&&amp…

    C++ 2023年4月17日
    00
  • 【Qt6】嵌套 QWindow

    在上个世纪的文章中,老周简单介绍了 QWindow 类的基本使用——包括从 QWindow 类派生和从 QRasterWindow 类派生。 其实,QWindow 类并不是只能充当主窗口用,它也可以嵌套到父级窗口中,变成子级对象。咱们一般称之为【控件】。F 话不多讲,下面咱们用实际案例来说明。 这个例子中老周定义了两个类: MyControl:子窗口对象,充…

    C++ 2023年5月2日
    00
  • C++文件处理

    ? 新建文件 //这是要操作的文件名称 string str_filename = “E:/data/t/haha.txt”; //创建一个流对象 o 就是从这个流对象出去, 出到哪里, 当然是我们要建立的文件 ofstream ofs; //out会覆盖 ofs.open(str_filename, ios::out); ofs << “我创建…

    C++ 2023年4月17日
    00
  • 【Visual Leak Detector】源码下载

    说明 使用 VLD 内存泄漏检测工具辅助开发时整理的学习笔记。本篇介绍 VLD 源码的下载。同系列文章目录可见 《内存泄漏检测工具》目录 目录 说明 1. 下载途径 2. 不同下载途径的源文件差异 1. 下载途径 以 v2.5.1 版本为例,可以到 Github-KindDragon-vld 页面下载 master 的 zip 源码包,如下所示: 也可以到 …

    C++ 2023年4月22日
    00
  • 面试最常问的数组转树,树转数组 c++ web框架paozhu实现

    刚毕业同学,找工作常被问 二维数组转树,树转二维数组 需要支持无限层级实现,如果你了解这个语言那么实现起来还要一番思考 c++ web框架 paozhu使用 需要实现数据库表数据到前台菜单实现,就是这种功能 二维数组转树,树转二维数组 保存时候树二维数组,展示时候树树状。 这个技术难点在于无限递归,这个树程序基本原理 现在看看c++怎么实现的,无限递归,家肯…

    C++ 2023年4月25日
    00
合作推广
合作推广
分享本页
返回顶部