梦想成为算法高手---基础算法篇:前缀和

从今天开始,我打算在博客中开设算法讲解方向的文章了,说是讲解,其实自身实力也偏弱所以打算在这个系列中分析分析自己的学习经历,以及一些生活上的趣事,希望和大家可以在往后的日子里共同进步吧.对于前缀和,我个人认为属于是算法中较为好理解,适合用于让初学者了解什么是算法?所以这边打算将其放在第一篇.那么,什么是前缀和?用最直白的话来讲,前缀和就是对于一个大小为n数组,计算前i个数字(0in)大小的总和即为前缀和.假设,在某种情况下,我们需要查找一个数组中某一段区间中所有数字的和,此时常规的写法为直接使用循环.其中,left和right为所需查询区间的位置(1leftrightn)在这里呢我们可以看到,在直接打暴力的情况下,单次查询时最坏情况下间复杂度来到了O(n),一旦题目变为多次查询(假设查询次数为m),时间复杂度会变为O(n*m),效率极其低下.在此,我们考虑前缀和:此种场景为前缀和最常见的情况,在多次查询前,我们可以对数据优先进行预处理对于数组从第一个元素到所有位置,我们先用一次循环计算出这些数值,在将他们存在一个数组(这里命名为prev)中,而后对于接下来的每一次查询区间总和都可以有ans prev[right] - prev[left-1],ans即为所需答案,此时时间复杂度降为O(nm).我们将前缀和数组 prev 的长度设为 n1(比原数组多开一位),核心是为了统一边界逻辑prev [i] 直接对应原数组前 i 个元素的总和,以 prev [0] 0 作为初始基准.这样既简化了首元素的前缀和计算,也能让区间求和公式对所有合法区间通用,不需要单独处理左端点为第一个元素的特殊情况.此种用法是最常见最简单的一种并非前缀和唯一的用法(比如二维前缀和、前缀和 哈希表统计子数组和、差分与前缀和的逆运算关系),在此不过多赘述.最后这里给出一易一难两题便于学习与理解前缀和:easy:【模板】前缀和hard:Problem - C2 - Codeforces题目的讲解我会放在下一次博客中,拜拜~