部分和(partial sum)在算法求解中的作用
2024-08-31 17:28:01
- C++ 的 STL 库的 <numeric> 头文件的 partial_sum 函数已实现了对某一序列的 partial sum。
- partial_sum(first, last, dest);
1. 部分和的引入
并非什么高级深奥的技巧,但却十分有用。
假设按照降序排列 N 个学生的考试成绩并保存到数组 scores[],现在想要编写求出从第 a 名到第 b 名成绩的函数 average(a, b),最简单的方法是,将 scores[a] 到 scores[b] 的乘积全部相加,然后除以 b-a+1。
这种方法的循环次数最大会达到 O(N)。如果只计算 1 次平均值,这种时复杂度就足够了。但多次调用 average() 的话,就需要对函数进行优化。
此时需要用到部分和(partial sum)(或者累加和)的概念。部分和就是,对从数组起始位置到当前任一位置求和并保存的数组(类似于概率理论中的分布函数的概念)。
pSum[j]=∑i=0jscores[i]
预先计算 psum 就能在 O(1) 时间内求出 scores[] 在特定区间的和(君子)。假设 psum[-1] = 0,那么,scores[a] 和 scores[b] 之间的和可按照如下方式计算:
psum[b]−psum[b−a+1]
部分和的简单计算:
int A[101], pSum[101], pSqSum[101];
sort(A, A+n);
pSum[0] = A[0];
pSqSum[0] = A[0]*A[0];
for (int i = 1; i < n; ++i){
pSum = pSum[i-1] + A[i];
pSqSum = pSqSum[i-1] + A[i]*A[i];
}
一定千万要注意,在求解某一区域的部分和的时候,比如 [a, b]
,pSum[a]
本身是包含数组在 a
处的值的,
// ∑_a^b A[i] ⇒
pSum[b] - (a == 0 ? 0 : pSum[a - 1]);
2. 均值、方差
v==1b−a+1∑i=ab(A[i]−μ)2∑i=abA[i]2b−a+1−μ2
3. 从一维到二维数组
记,psum[y,x]=∑i=0y∑j=0xA[i,j],则从 (y1,x1) 到 (y2,x2) 之间矩形所包含元素的和,
sum([y1,x1],[y2,x2])=psum(y2,x2)−psum(y2−1,x1)−psum(y1,x2−1)+psum(y1−1,x1−1)
int gridSum(const vector<vector<int>>& psum, int y1, int x1, int y2, int x2) {
int ret = psum[y2][x2];
if (y1 > 0) ret -= psum[y1-1][x2];
if (x1 > 0) ret -= psum[y2][x1-1];
if (x1 > 0 && y1 > 0) ret += psum[y1-1][x1-1];
return ret;
}
最新文章
- 在iOS中实现一个简单的画板App
- dispatcherServlet 真正处理请求的源码解析
- 使用jquery-qrcode生成二维码
- MINIX3
- hibernate(1)
- Java工程为什么要加一个biz层
- android: 从相册中选择照片
- 基于theano的深度卷积神经网络
- Hadoop对文本文件的快速全局排序
- EXCEL VBA运行不显示系统提示
- [每日一题] OCP1z0-047 :2013-08-29 NULL............................................................168
- (转)JAVA 调用Web Service的三种方法
- NetMQ
- javascript 函数 add(1)(2)(3)(4)实现无限极累加 —— 一步一步原理解析
- 【JAVAWEB学习笔记】29_文件的上传------commons-fileupload
- 微信浏览器返回刷新,监听微信浏览器返回事件,网页防复制,移动端禁止图片长按和vivo手机点击img标签放大图片
- Jsoup解析XML
- 六、SpringBoot与数据访问
- vue路由6:导航钩子
- Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals) Problem D (Codeforces 831D) - 贪心 - 二分答案 - 动态规划
热门文章
- Postman APP
- 12、UVC&;V4L2的关系
- find---查找文件或目录
- 阿里云 Ubuntu14.04 升级 python3.4 到 python 3.5/6
- 洛谷 P1957 口算练习题
- 例说linux内核与应用数据通信(四):映射设备内核空间到用户态
- Eclipse中Git插件使用技巧:[5]还原文件
- 5.9 enum--支持枚举类型
- KNIMI数据挖掘建模与分析系列_002_利用KNIMI做商超零售关联推荐
- poi完美word转html(表格、图片、样式)