首页 > 其他分享 >前缀和

前缀和

时间:2023-04-23 19:40:29浏览次数:27  
标签:前缀 sum prefix 查询 算法 数组

介绍

前缀和算法是一种优化技巧,常用于解决数组问题中的查询操作,例如区间求和、区间最大值/最小值等。其基本思路是先预处理出一个前缀和数组,在需要查询时通过计算前缀和数组的差值来得到查询结果。这个算法可以在O(1)的时间内回答很多查询问题,因此在实际编程中被广泛使用。

起源

前缀和算法的起源可以追溯到卡特兰数学家 Eugène Charles Catalan 在 1878 年提出的连续子序列问题。该问题要求在一个长度为 n 的数组中,找出所有连续子序列的和,并统计其中等于某个给定值的子序列的数量。Catalan 发现,如果先计算出数组的前缀和,则任意两个位置之间的子序列和可以通过前缀和数组的差值计算得出。通过这个思路,他成功地解决了这个问题,并将前缀和算法推广到更广泛的应用领域。

用法

前缀和算法是一种常用于数组问题的优化技巧,可以在O(1)的时间内回答很多查询问题,例如区间求和、区间最大值/最小值等。

C语言前缀和算法的基本思路是:先预处理出一个前缀和数组 prefix_sum,其中 prefix_sum[i] 表示原始数组 nums 的前 i 个元素的和;然后在需要查询时,通过计算 prefix_sum 的差值来得到查询结果。

代码

#include <stdio.h>

const int MAXN = 100005;
int nums[MAXN], prefix_sum[MAXN];

int main() {
    int n;
    scanf("%d", &n);

    // 输入原始数组
    for (int i = 1; i <= n; i++) {
        scanf("%d", &nums[i]);
    }

    // 预处理前缀和数组
    for (int i = 1; i <= n; i++) {
        prefix_sum[i] = prefix_sum[i-1] + nums[i];
    }

    // 查询区间 [l, r] 的和
    int l, r;
    scanf("%d %d", &l, &r);
    printf("区间 [%d, %d] 的和为:%d\n", l, r, prefix_sum[r] - prefix_sum[l-1]);

    return 0;
}

解析

上述代码中,我们首先定义了一个长度为 MAXN 的整型数组 nums 和 prefix_sum,其中 nums 存储原始数组,prefix_sum 存储前缀和数组。在主函数中,我们先读入原始数组 nums,并且计算出前缀和数组 prefix_sum。这里需要注意的是,为了方便计算,我们将 prefix_sum[0] 初始化为 0,这样求解 prefix_sum[i] 就不需要判断 i 是否等于 0。

在查询区间 [l, r] 的和时,我们可以直接用 prefix_sum[r] - prefix_sum[l-1] 计算出答案。这个式子的意思是,区间 [l, r] 的和等于前 r 个元素的和 prefix_sum[r] 减去前 l-1个元素的和 prefix_sum[l-1]。由于 prefix_sum[0] 已经预处理为 0,所以我们可以使用 prefix_sum[l-1] 而不必担心越界问题。

除了求和之外,前缀和算法还可以用来回答很多其他类型的查询问题,例如查询区间最大值/最小值、统计区间内元素个数等。通过巧妙地设计前缀和数组,我们可以在O(n)的时间内预处理出所有需要查询的结果,在O(1)的时间内回答每次查询,从而大大提高程序的效率。

前缀和_数组

标签:前缀,sum,prefix,查询,算法,数组
From: https://blog.51cto.com/u_16085497/6218460

相关文章

  • 七、最长公共前缀
    编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""。示例 1:输入:["flower","flow","flight"]输出:"fl"示例 2:输入:["dog","racecar","car"]输出:""解释:输入不存在公共前缀。说明:所有输入只包含小写字母 a-z 。......
  • 前缀和
    算法简介前缀和用于快速得到数组某个连续区间内所有元素的元素和。时间复杂度构建前缀和数组:\(O(n)\)求取某区间总和:\(O(1)\)实现原理按照如下规则构建前缀和数组:例如:有数组\(a\),前缀和数组为\(s\)。\(s[0]=0\)\(s[1]=a[1]\)\(s[2]=a[2]+a[1]\)...\(s[n]=......
  • 一维与二维前缀和(蓝桥杯复习+例题讲解+模板c++)
    文章目录前缀和二维前缀和总结3956.截断数组99.激光炸弹前缀和前缀和是一种常见的算法,用于快速计算数组中某一段区间的和。前缀和的思想就是预处理出数组中前缀和,然后用后缀和减去前缀和,即可快速计算区间和。以一维数组为例,设表示数组中第个元素的值,表示数组中前个元素的......
  • 【ACM算法竞赛日常训练】DAY16【奇♂妙拆分】【区区区间间间】【小AA的数列】数学 |
    DAY16共3题:奇♂妙拆分(简单数学)区区区间间间(单调栈)小AA的数列(位运算dp)......
  • 【前缀和】LeetCode 523. 连续的子数组和
    题目链接523.连续的子数组和思路参考宫水三叶大佬题解一开始以为和Leetcode53MaximumSubarray思路差不多,都是求子数组的值。但是后来发现在53题中并没有求出每个子数组的和,只是在贪心的情况下求出了可能的最大和代码classSolution{publicbooleancheckSubarra......
  • LeetCode 周赛 340,质数 / 前缀和 / 极大化最小值 / 最短路 / 平衡二叉树
    本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]提问。大家好,我是小彭。上周跟大家讲到小彭文章风格的问题,和一些朋友聊过以后,至少在算法题解方面确定了小彭的风格。虽然竞赛算法题的文章受众非常小,但却有很多像我一样的初学者,他们有兴趣参加但容易被题目难......
  • 【前缀和】LeetCode 1031. 两个非重叠子数组的最大和
    题目链接1031.两个非重叠子数组的最大和思路代码classSolution{publicintmaxSumTwoNoOverlap(int[]nums,intfirstLen,intsecondLen){//求一个前缀和for(inti=1;i<nums.length;++i){nums[i]+=nums[i-1];}......
  • 前缀和
    链接:https://ac.nowcoder.com/acm/contest/55407/E来源:牛客网给定n个整数a1,a2,···,an ,求它们两两相乘再相加的和,即S=a1 ·a2 +a1 ·a3 +···+a1 ·an +a2 ·a3 +···+an-2 ·an-1 +an-2 ·an +an-1 ·an.输入描述:#inc......
  • 前缀和与差分
    1.K倍区间来源:第八届蓝桥杯省赛C++B组,第八届蓝桥杯省赛JAVAB组原题链接题目描述给定一个长度为\(N\)的数列,\(A_1,A_2,…A_N\),如果其中一段连续的子序列\(A_i,A_{i+1},…A_j\)之和是\(K\)的倍数,我们就称这个区间\([i,j]\)是\(K\)倍区间。你能求出数列中总共有多......
  • 前缀和-leetcode303
    LeetCode上的题目"303.区域和检索-数组不可变",是一个相对简单的问题。问题描述:给定一个整数数组nums,求出该数组从索引i到j(i≤j)范围内元素的总和,包含i,j两点。实现NumArray类:NumArray(int[]nums)用整数数组nums初始化对象intsumRange(inti,intj)返回......