前缀和

前缀和

一、介绍

前缀,顾名思义就是一个东西前面的点缀...(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日

相关文章

  • 【Visual Leak Detector】核心源码剖析(VLD 2.5.1)

    说明 使用 VLD 内存泄漏检测工具辅助开发时整理的学习笔记。本篇对 VLD 2.5.1 源码做内存泄漏检测的思路进行剖析。同系列文章目录可见 《内存泄漏检测工具》目录 目录 说明 1. 源码获取 2. 源码文件概览 3. 源码剖析 3.1 通过 inline hook 修补 LdrpCallInitRoutine 3.2 通过 IAT hook 替换内存操…

    C++ 2023年5月11日
    00
  • linux开发之gdb记录

    简述 GDB, the GNU Project debugger, allows you to see what is going on ‘inside’ another program while it executes — or what another program was doing at the moment it crashed.GDB, G…

    C++ 2023年4月17日
    00
  • 【Visual Leak Detector】源码文件概览

    说明 使用 VLD 内存泄漏检测工具辅助开发时整理的学习笔记。本篇对 VLD 源码包中的各文件用途做个概述。同系列文章目录可见 《内存泄漏检测工具》目录 目录 说明 1. 整体概览 2. 文件夹 .teamcity 3 文件夹 lib 3.1 文件夹 cppformat(生成 libformat) 3.2 文件夹 dbghelp 3.3 文件夹 gtest(…

    C++ 2023年4月24日
    00
  • 最短路径问题

    平面上有n个点(n<=100),每个点的坐标均在-10000~10000之间,其中的一些点之间有连线。 若有连线,则表示可从一个点到达另一个点,即两点间有通路,同路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。 小提示: 两点的距离:如果点\(A\)坐标为\((x_A,y_A)\),点\(B\)的坐标为\((x_B,y_B)\),\…

    C++ 2023年4月24日
    00
  • 【Visual Leak Detector】使用注意事项

    说明 使用 VLD 内存泄漏检测工具辅助开发时整理的学习笔记。本篇介绍使用 VLD 时的注意事项。同系列文章目录可见 《内存泄漏检测工具》目录 目录 说明 1. 官网文档 2. 注意事项 1. 官网文档 可以在 Using-Visual-Leak-Detector 官方文档里看到如何使用 VLD,里面介绍了如何在 Visual C++ 2003/2005/2…

    C++ 2023年4月17日
    00
  • 【Visual Leak Detector】源码调试 VLD 库

    说明 使用 VLD 内存泄漏检测工具辅助开发时整理的学习笔记。本篇介绍 VLD 源码的调试。同系列文章目录可见 《内存泄漏检测工具》目录 目录 说明 1. VLD 库源码调试步骤 1.1 设置为启动项目 1.2 设置调试程序 1.3 设置输出目录 1.4 拷贝 vld 依赖文件 1.5 加断点调试 2. 注意事项 1. VLD 库源码调试步骤 以 vld2.…

    C++ 2023年5月7日
    00
  • 如何将 Spire.Doc for C++ 集成到 C++ 程序中

    Spire.Doc for C++ 是一个专业的 Word 库,供开发人员在任何类型的 C++ 应用程序中阅读、创建、编辑、比较和转换 Word 文档。 本文演示了如何以两种不同的方式将 Spire.Doc for C++ 集成到您的 C++ 应用程序中。 通过 NuGet 安装 Spire.Doc for C++ 通过手动导入库安装 Spire.Doc f…

    C++ 2023年4月27日
    00
  • STL 容器 002 (vector 详解)

    为什么 各方面表现都比较中等, 适用范围广 尾插很快, 查找也比较快 是什么 动态数组 特点: 动态数组, 三个指针控制 两倍增长 扩充的方法: 不能原地扩充, 因为后面可能会有其他的东西, 必须在 其他地方开辟一块更大的内存 提供[] 所有的有连续空间的容器都有[] iterator是class类型的 怎么样 制造 两倍增长 //push_back() 检…

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