前缀和&二维前缀和
2024-09-01 00:59:10
我们知道，数组上的前缀和S[i]=S[i-1]+a[i]
那么，怎样求二维前缀和呢？
二维前缀和：
绿色点的前缀和就是黄色、红色、灰色和绿色的点权和
怎样计算？
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
绿色部分的前缀和=（红色+灰色）+（黄色+灰色）-灰色+绿色
有了前缀和，怎样计算某一部分的点权和呢？
类似的，现在绿色部分的总和=S(4,4)-S(4,2)-S(2,4)+S(2,2)
我们设绿色部分的边长为rx*ry,a为总和，绿色部分右下角坐标为i,j
a[i][j]=s[i][j]-s[i-rx-1][j]-s[i][j-1-ry]+s[i-1-rx][j-1-ry];
最新文章
- windows server 2012 使用问题
- 【.net+jquery】绘制自定义表单（含源码）
- LDAP与禅道
- 前端构建工具 webpack
- 工具:使用jekyll生成静态网站
- SpringMVC学习系列（7） 之 格式化显示
- JavaScript封装Ajax（类JQuery中$.ajax()方法）
- dynamic基元类型
- React-组件嵌套-子组件通过委托向父组件传值
- lintcode ：Count 1 in Binary 二进制中有多少个1
- Sina App Engine(SAE)入门教程(7)- Storage使用
- win32 api ShouCursor 根据内部计数器 是否>= 0 决定是否 显示光标，每true时计数器+1，每false-1
- windows server 2003 取消登录Ctrl+Alt+delete
- ios之TableViewCell重用机制避免反复显示问题
- Java "double字符串转数字"
- 利用Lua读写本地文件
- JSON 数据转换
- Sqlite3-安装使用
- JDBC-Oracle连接教程
- Date对象的用法总结