代码编织梦想

用途

假如一个数组,需要大量去查询他的前n项和、x–y项的和,这样可以先列出所有数组和,查询时候不用每次遍历,节省时间。
方法有两种,第一种是二维数组,第二种一维数组。

第一种方法

第一种方法
如图是第一种方法所建表示意图,这样算出了任意两个之间的和,只需调用一次即可。

第二种方法

在这里插入图片描述
若查询x—y之间的和,需要查询后求差值。

比较

一般而言,方法二更好。
但若查询量非常巨大,采用第一种。

代码

#include <iostream>
using namespace std;

int Random_array(int* a, int n)
{
	srand((unsigned int)time(NULL));
	for (int i = 0; i < n; i++)
		a[i] = rand() % 100;
	return *a;
}

void Print_array(int* a, int n)
{
	for (int i = 0; i < n; i++)
		printf("%d ,", a[i]);
	printf("\n");
}

int* Sub_Array_Sum(int* a, int n)
{
	int* b = new int[n];
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		sum += a[i];
		b[i] = sum;
	}
	return b;
}


int main()
{
	int a[10] = {};
	Random_array(a, 10);
	Print_array(a, 10);
	int* b = Sub_Array_Sum(a, 10);
	Print_array(b, 10);
	int num = 0;
	printf("求前x个的和,请输入x=");
	scanf_s("%d", &num);
	printf("前%d个的和为:%d", num, b[num - 1]);
	int x = 0, y = 0;
	printf("\n求x--y的和,请输入x与y");
	cin >> x >> y;
	printf("%d到%d的和为:%d", x, y, b[y] - b[x - 1]);//此处偷懒了,应该判断x是否为0

	return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Ws_Te47/article/details/127168691

前缀和——(2)二维数组前缀和-爱代码爱编程

前面部分我们介绍了一维前缀和https://blog.csdn.net/justidle/article/details/103524440。下面我们扩展一下,来介绍二维前缀和。 什么是二维前缀和 比如我们有这样一个矩阵a,如下所示: 1 2 4 3 5 1 2 4 6 3 5 9 我们定义一个矩阵sum,其中,那么这个矩阵就是这样的: 1 3

leetcode刷题(一)_数组类_7&8:二维数组变换、前缀和数组-爱代码爱编程

二维数组变换、前缀和数组 涉及题目总结 涉及题目 二维数组变换566-重塑矩阵-简单、48-旋转图像-中等、73-矩阵置零-中等、289-生命游戏-中等前缀和数组303-区域和检索-数组不可变-简单、304-二维区域和检索-矩阵不可变 -中等、238-除自身以外数组的乘积-中等总结 289有点意思,由于数组元素的值非0即1,那么只有int的

如何求二维数组的前缀和?-爱代码爱编程

什么是前缀和? 前缀和是一种重要的预处理,能大大降低查询的时间复杂度。我们可以简单理解为“数列的前 n 项的和”。这个概念其实很容易理解,即一个数组中,第 n 位存储的是数组前 n 个数字的和。 通过一个例子来进行说明会更清晰。题目描述:有一个长度为 N 的整数数组 A,要求返回一个新的数组 B,其中 B 的第 i 个数 B[i]是「原数组 A

算法:一维数组前缀和-爱代码爱编程

定义: arr[]为一个数组 sum[i]为 arr 0到i的前缀和 sum[i]=sum[i-1]+arr[i],i>0 sum[0]=arr[0],i=0 要求L到R的区间和 sum[L,R]等于sum[R]-sum[L-1] (L>0) sum[L,R]=sum[R] (L=0) 代码如下: #include<iostream&g

从前缀和数组到树状数组-爱代码爱编程

前缀和 前缀和数组: 初始化:O(n)时间复杂度,顺序扫描原数组即可 查询区间和:O(1)时间复杂度,S[j]-S[i]即为原数组i到j的区间和 单点修改:O(n)时间复杂度,需要修改S[i]~S[n]的所有值 慢,是因为S[i]的值与之前原数组中所有项都有关系 弱化这种关系,即可加快单点修改速度,当然也会丧失部分查询速度,但是这种取舍是值得的。

小而美的算法技巧:前缀和数组-爱代码爱编程

学算法认准 labuladong 后台回复 进群 进刷题 读完本文,可以去力扣解决如下题目: 303. 区域和检索 - 数组不可变(中等) 304. 二维区域和检索 - 矩阵不可变(中等) 560. 和为K的子数组(中等) PS:这是两年前发布的 前缀和技巧:解决子数组问题,我优化并添加了很多内容,这里重新发一遍。 前缀和技

力扣刷题之路------二维数组变换、前缀和数组-爱代码爱编程

刷题顺序参考:力扣刷题顺序 涉及题目 48. 旋转图像73. 矩阵置零289. 生命游戏238. 除自身以外数组的乘积 48. 旋转图像 自己的解题思路: 题目上说不能使用另一个矩阵来旋转图像,那就只能一个一个的换位置了。和之前的一维数组向右移动三个的题目的想法差不多,可以看出来每次数组都会变四个,比如上图的n=3的时候,先变换位置的是四个

前缀和数组-爱代码爱编程

前缀和 前言一、前缀和理解二、原理与代码2.1 一维数组的前缀和2.2 二维数组的前缀和三、典型例题四、补充知识1、构造函数2、修饰符范围3、二维数组 前言     本文是基于labuladong算法秘籍的学习总结,是算法总结中的数组与链表篇章,其他篇章以及资料下载在算法学习总结目录中下载,传送门:算法学习总结   本人是算法菜鸟一枚,通过在

前缀和数组与差分数组-爱代码爱编程

首先,介绍一下前缀和数组与差分数组是干什么用的,它们主要用在对数组中某一区间中的元素进行操作,例如对a数组中第10到20这个区间中的每一个元素都加上一个数,或者求该区间中所有元素的和,你可能会想到利用对数组进行遍历来实现,但是如果当数据量很大的时候,显然这个方法有些笨拙(时间复杂度过高,提交oj时可能会超时)了,于是就有了下面我们要利用的前缀和数组与差分数

二维数组前缀和_guohy.的博客-爱代码爱编程

二维数组前缀和 对于二维数组求前缀和,我们先预处理第一行跟第一列的前缀和 第一行跟第一列的前缀和可以看作一维数组的前缀和 前缀和数组的0,0等于原数组的0,0,第一行为原数组第一行的前缀和,第一列为第一列的前缀和 预处理: //原数组 int arr[110][110]={ {}, {0,1,2,3,4,5,6,

数组-一文搞定前缀和数组_xichengl的博客-爱代码爱编程

前言   就从数组开始,以后会一直更新算法。数组有下图这些知识点与技巧。本文主要讲解其中的前缀和知识点。   思路   适合的场景:原始数组不会被修改,且频繁查询某个区间的累加和。   创建一个prefixSum数组,长度比原数组nums长度多1。prefixSum[i]存储nums[0]到nums[i]的和。   尤其要注意prefixSum

智乃酱的cube(线段树维护)_一条小小yu的博客-爱代码爱编程

智乃酱有n个cube(立方体),一开始,这些立方体的长宽高均为1,也就是它们的体积都为1×1×1=1,并且这些立方体从1到n排成一排。 接下来智乃酱将要进行m次操作。智乃酱可以将l到r这个区间内所有的立方体某个维度增加a,或者向你询问从l到r中所有立方体的体积之和。 由于这个数字比较大,所以每次查询时你只用输出从l到r中所有立方体的体积之和mod 10^