• / 16
  • 下载费用:4 金币  

二维树状数组2

关 键 词:
二维树状数组
资源描述:
二维树状数组 胡伟栋 树状数组 • 问题: – 有一个数列{an},给出一种操作序列,每次可 以改变数列中的一个元素的值 – 要求动态维护,使得任何时刻都能用较快速度 求出数列的部分和 树状数组 • 令t[i]=a[x-lowbit(i)i]的和 • 则S[i]=t[i]+S[lowbit(i)] – S[i]表示a[i]的部分和 – S[i]=sigma{t[x(i)k]} • x(i)0=i • x(i)1=x(i)0-lowbit(x(i)0) • x(i)2=x(i)1-lowbit(x(i)1) • …… 树状数组 • 当更新a[i]时,需要更新 – t[y(i)0] y(i)0=i – t[y(i)1] y(i)1=y(i)0+lowbit(y(i)0) – t[y(i)2] y(i)2=y(i)1+lowbit(y(i)1) – …… 树状数组 13 1415 16 9 1011 12 5 67 8 1 23 4 二维树状数组 • 问题 – 给出矩阵{aij} – 可以随时改变矩阵某一个位置的值 – 要求能随时求出矩阵中某一个连续子矩阵的和 二维树状数组 • 此问题和原来的问题很像,只是由一维变 成了二维 • 需要对原来的数据结构进行改进,以适应 新的要求 二维树状数组 • 改进 – 用t[i,j]表示a[i-lowbit(i)+1i, j-lowbit(j)+1j]的 和 – S[i,j]=? 二维树状数组 • 计算 S[15,15] 123456789 101112131415 14 13 12 11 10 9 8 7 6 5 4 3 2 1 二维树状数组 • S[i,j]= – sigma{t[x(i)k, x(j)l]} 二维树状数组 • 更新a[i, j] – 需要更新t[y(i)k, y(j)l] 二维树状数组 123456789 1 0 1 1 1 2 131 4 1 5 1 4 1 3 1 2 1 1 1 0 9 8 7 6 5 4 3 2 1 • 更新 a[1,1] 二维树状数组 • 程序实现 – update(i, j, v) • add(i, j, v-old[i, j]); – add(i, j, v) • j0j • while (i0) • jj0 • while (j0) – sum+=t[i,j] – j&=j-1 • i&=i-1 二维树状数组 • 复杂度 – 单个操作 O(log2max) 例 • 有一个线段盒子 – A x y 表示插入一条[x,y]线段 – D x y 表示删除一条[x,y]线段,如果当前盒子里 没有,就什么也不做 – S x y 表示要求出完全在[x,y]区间的线段数 • 命令数105 • 1=x,y=1000
展开阅读全文
  麦档网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:二维树状数组2
链接地址:https://www.maidoc.com/p-15683729.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2018-2020 maidoc.com版权所有  文库上传用户QQ群:3303921 

麦档网为“文档C2C模式”,即用户上传的文档所得金币直接给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的金币归上传人(含作者)所有。
备案号:蜀ICP备17040478号-3  
川公网安备:51019002001290号 

本站提供办公文档学习资料考试资料文档下载


收起
展开