当前位置: 首页 > news >正文

经典网站欣赏、推广营销app

经典网站欣赏、,推广营销app,南平网站设计,网站便民服务平台怎么做在算法竞赛与日常编程中,前缀和是一种极为实用的预处理技巧,能显著提升处理区间和问题的效率。今天,我们就来深入剖析一维前缀和与二维前缀和这两个经典模板。 一、【模板】一维前缀和 题目描述 给定一个长度为 n n n 的整数数组 a a a&…

在算法竞赛与日常编程中,前缀和是一种极为实用的预处理技巧,能显著提升处理区间和问题的效率。今天,我们就来深入剖析一维前缀和与二维前缀和这两个经典模板。

一、【模板】一维前缀和

题目描述

给定一个长度为 n n n 的整数数组 a a a,我们需要完成以下两个任务:

  1. 预处理数组,得到前缀和数组。
  2. 能够快速查询数组中任意区间 [ l , r ] [l, r] [l,r] 0 ≤ l ≤ r < n 0 \leq l \leq r < n 0lr<n)内所有元素的和。

算法原理

一维前缀和的核心思想是预先计算数组中每个位置之前所有元素的总和。设前缀和数组为 s s s,其中 s [ i ] s[i] s[i] 表示数组 a a a 中前 i i i 个元素的和( i i i 1 1 1 开始),那么有递推公式:
[s[i] = s[i - 1]+a[i - 1]]
这里 s [ 0 ] = 0 s[0]=0 s[0]=0,是为了方便处理边界情况。

当我们需要查询区间 [ l , r ] [l, r] [l,r] 的和时,根据前缀和的性质,该区间的和可以通过 s [ r + 1 ] − s [ l ] s[r + 1]-s[l] s[r+1]s[l] 快速得到。这是因为 s [ r + 1 ] s[r + 1] s[r+1] 包含了前 r + 1 r + 1 r+1 个元素的和, s [ l ] s[l] s[l] 包含了前 l l l 个元素的和,两者相减就得到了区间 [ l , r ] [l, r] [l,r] 的和。

在这里插入图片描述

在这里插入图片描述

C++ 代码实现

#include <iostream>
#include <vector>using namespace std;// 计算一维前缀和数组
vector<int> calculatePrefixSum(const vector<int>& a) {int n = a.size();vector<int> s(n + 1, 0);for (int i = 1; i <= n; ++i) {s[i] = s[i - 1] + a[i - 1];}return s;
}// 查询区间 [l, r] 的和
int querySum(const vector<int>& s, int l, int r) {return s[r + 1] - s[l];
}int main() {vector<int> a = {1, 2, 3, 4, 5};vector<int> s = calculatePrefixSum(a);int l = 1, r = 3;cout << "The sum of the interval [" << l << ", " << r << "] is: " << querySum(s, l, r) << endl;return 0;
}

复杂度分析

  • 时间复杂度:计算前缀和数组的时间复杂度为 O ( n ) O(n) O(n),因为需要遍历数组一次。每次查询区间和的时间复杂度为 O ( 1 ) O(1) O(1),这使得在多次查询的场景下,一维前缀和算法具有很高的效率。
  • 空间复杂度:需要额外的长度为 n + 1 n + 1 n+1 的数组来存储前缀和,因此空间复杂度为 O ( n ) O(n) O(n)

二、【模板】二维前缀和

题目描述

给定一个 m × n m \times n m×n 的二维整数矩阵 A A A,我们要完成以下任务:

  1. 预处理矩阵,得到二维前缀和矩阵。
  2. 能够快速查询矩阵中任意子矩阵 [ ( x 1 , y 1 ) , ( x 2 , y 2 ) ] [(x_1, y_1), (x_2, y_2)] [(x1,y1),(x2,y2)] 0 ≤ x 1 ≤ x 2 < m 0 \leq x_1 \leq x_2 < m 0x1x2<m 0 ≤ y 1 ≤ y 2 < n 0 \leq y_1 \leq y_2 < n 0y1y2<n)内所有元素的和。

算法原理

对于二维前缀和,我们定义 S [ i ] [ j ] S[i][j] S[i][j] 表示矩阵 A A A 中从左上角 ( 0 , 0 ) (0, 0) (0,0) 到右下角 ( i − 1 , j − 1 ) (i - 1, j - 1) (i1,j1) 这个子矩阵内所有元素的和( i i i j j j 1 1 1 开始)。其递推公式如下:
S [ i ] [ j ] = S [ i − 1 ] [ j ] + S [ i ] [ j − 1 ] − S [ i − 1 ] [ j − 1 ] + A [ i − 1 ] [ j − 1 ] S[i][j]=S[i - 1][j]+S[i][j - 1]-S[i - 1][j - 1]+A[i - 1][j - 1] S[i][j]=S[i1][j]+S[i][j1]S[i1][j1]+A[i1][j1]
这里减去 S [ i − 1 ] [ j − 1 ] S[i - 1][j - 1] S[i1][j1] 是为了避免重复计算。

当查询子矩阵 [ ( x 1 , y 1 ) , ( x 2 , y 2 ) ] [(x_1, y_1), (x_2, y_2)] [(x1,y1),(x2,y2)] 的和时,公式为:
s u m = S [ x 2 + 1 ] [ y 2 + 1 ] − S [ x 1 ] [ y 2 + 1 ] − S [ x 2 + 1 ] [ y 1 ] + S [ x 1 ] [ y 1 ] sum = S[x_2 + 1][y_2 + 1]-S[x_1][y_2 + 1]-S[x_2 + 1][y_1]+S[x_1][y_1] sum=S[x2+1][y2+1]S[x1][y2+1]S[x2+1][y1]+S[x1][y1]

在这里插入图片描述

在这里插入图片描述

C++ 代码实现

#include <iostream>
#include <vector>using namespace std;// 计算二维前缀和矩阵
vector<vector<int>> calculateTwoDPrefixSum(const vector<vector<int>>& A) {int m = A.size();int n = A[0].size();vector<vector<int>> S(m + 1, vector<int>(n + 1, 0));for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + A[i - 1][j - 1];}}return S;
}// 查询子矩阵 [(x1, y1), (x2, y2)] 的和
int queryTwoDSum(const vector<vector<int>>& S, int x1, int y1, int x2, int y2) {return S[x2 + 1][y2 + 1] - S[x1][y2 + 1] - S[x2 + 1][y1] + S[x1][y1];
}int main() {vector<vector<int>> A = {{1, 2, 3},{4, 5, 6},{7, 8, 9}};vector<vector<int>> S = calculateTwoDPrefixSum(A);int x1 = 0, y1 = 0, x2 = 1, y2 = 1;cout << "The sum of the sub - matrix [(" << x1 << ", " << y1 << "), (" << x2 << ", " << y2 << ")] is: "<< queryTwoDSum(S, x1, y1, x2, y2) << endl;return 0;
}

复杂度分析

  • 时间复杂度:计算二维前缀和矩阵需要两层嵌套循环遍历矩阵,时间复杂度为 O ( m × n ) O(m \times n) O(m×n)。每次查询子矩阵和的时间复杂度为 O ( 1 ) O(1) O(1),这使得在多次查询子矩阵和的场景下,二维前缀和算法非常高效。
  • 空间复杂度:需要额外的 ( m + 1 ) × ( n + 1 ) (m + 1)\times(n + 1) (m+1)×(n+1) 大小的矩阵来存储二维前缀和,因此空间复杂度为 O ( m × n ) O(m \times n) O(m×n)

通过以上的讲解和代码实现,我们可以看到前缀和算法在处理区间和与子矩阵和问题时的强大威力。它通过预处理的方式,将原本可能需要 O ( n ) O(n) O(n) O ( m × n ) O(m\times n) O(m×n) 时间复杂度的查询操作优化到了 O ( 1 ) O(1) O(1),在实际应用中能显著提升程序的性能。希望大家能够熟练掌握这两个模板,并在后续的算法学习和实践中灵活运用。

http://www.tj-hxxt.cn/news/32303.html

相关文章:

  • 怎么做电商网站重要新闻今天8条新闻
  • 做公司网站建设价格南京网站设计公司
  • 销售机械设备做网站网络营销的定义
  • 上饶做网站要多少钱私人网站服务器
  • 刚做网站做多用户还是单用户珠海百度关键字优化
  • 目前网站开发 用java 还是phpseo公司哪家好用
  • 如何分析一个网站做的怎么样管理培训
  • 网站后台登陆验证码东莞seo优化推广
  • 京东商城网站的搜索引擎营销做的案例分析天津谷歌优化
  • 郑州网站建设公司招聘seo外链代发
  • 请稍后重试(3008)排名优化是怎么做的
  • 机械类网站模板长沙有实力的关键词优化价格
  • 拍卖网站开发线上营销推广方式
  • 域名做网站自己的电脑网站排名推广工具
  • 亿网中国网站管理系统seo入门教程网盘
  • 网站维护工作台湾搜索引擎
  • 优化网站排名方法教程站长工具果冻传媒
  • 随州制作网站如何让百度收录自己信息
  • 想通过网站卖自己做的东西app软件开发
  • 做个有用网站搜索引擎推广的费用
  • 百能网是哪家公司做的网站上海疫情突然消失的原因
  • 上线了 做商务网站开封网站推广公司
  • 企业招聘网站推广渠道怎么写
  • 公司网站域名解析谁来做营销培训视频课程免费
  • 网站开发需求用什么软件seo入口
  • 个体户做网站有用吗百度指数的数值代表什么
  • 找个靠谱网站做推广推广计划方案模板
  • 云南凡科建站哪家好百度官网网站
  • 疫情又要来了吗最新消息十堰seo优化
  • 淘客做网站的软件全网热搜关键词排行榜