- 浏览: 580740 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
一、树状数组是干什么的?
平常我们会遇到一些对数组进行维护查询的操作,比较常见的如,修改某点的值、
求某个区间的和,而这两种恰恰是树状数组的强项!当然,数据规模不大的时候,对于修改某点的值是非常容易的,复杂度是O(1),但是对于求一个区间的和就要扫一遍了,复杂度是O(N),如果实时的对数组进行M次修改或求和,最坏的情况下复杂度是O(M*N),当规模增大后这是划不来的!而树状数组干同样的事复杂度却是O(M*lgN),别小看这个lg,很大的数一lg就很小了。
二、树状数组的定义
如图所示,红色矩形表示的数组C[]就是树状数组。
给定序列(数列)A,我们设一个数组C满足
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
……
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16
......
定义:
C[t] = A[t – 2^k + 1] + … + A[t],k为t在二进制下末尾0的个数。(t>=1)
分析上面的几组式子可知,当 t 为奇数时,Ct=Ai ;当 t为偶数时,就要看 t的因子中最多有二的多少次幂,例如,6 的因子中有 2 的一次幂,等于 2 ,所以 C6=A5+A6(由六向前数两个数的和),4 的因子中有 2 的两次幂,等于 4 ,所以 C4=A1+A2+A3+A4(由四向前数四个数的和)。
三、基本操作
(1)C[t]展开以后有多少项?由下面公式计算:
(2)修改
当我们修改A[i]的值时,可以从C[i]往根节点一路上溯,调整这条路上的所有C[]即可,对于节点i,父节点下标 p=i+lowbit(i)
平常我们会遇到一些对数组进行维护查询的操作,比较常见的如,修改某点的值、
求某个区间的和,而这两种恰恰是树状数组的强项!当然,数据规模不大的时候,对于修改某点的值是非常容易的,复杂度是O(1),但是对于求一个区间的和就要扫一遍了,复杂度是O(N),如果实时的对数组进行M次修改或求和,最坏的情况下复杂度是O(M*N),当规模增大后这是划不来的!而树状数组干同样的事复杂度却是O(M*lgN),别小看这个lg,很大的数一lg就很小了。
二、树状数组的定义
如图所示,红色矩形表示的数组C[]就是树状数组。
给定序列(数列)A,我们设一个数组C满足
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
……
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16
......
定义:
C[t] = A[t – 2^k + 1] + … + A[t],k为t在二进制下末尾0的个数。(t>=1)
分析上面的几组式子可知,当 t 为奇数时,Ct=Ai ;当 t为偶数时,就要看 t的因子中最多有二的多少次幂,例如,6 的因子中有 2 的一次幂,等于 2 ,所以 C6=A5+A6(由六向前数两个数的和),4 的因子中有 2 的两次幂,等于 4 ,所以 C4=A1+A2+A3+A4(由四向前数四个数的和)。
三、基本操作
(1)C[t]展开以后有多少项?由下面公式计算:
int lowbit(int t){//计算c[t]展开的项数 return t&(-t); } 例: lowbit(1)=1 C1 = A1 lowbit(2)=2 C2 = A1 + A2 lowbit(3)=1 C3 = A3 lowbit(4)=4 C4 = A1 + A2 + A3 + A4 lowbit(5)=1 C5 = A5 lowbit(6)=2 C6 = A5 + A6 lowbit(7)=1 C7 = A7 lowbit(8)=8 C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 ....... c[t]展开的项数就是lowbit(t),c[t]就是从a[t]开始往左连续求lowbit(t)个数的和, lowbit(1)=1 lowbit(2)=2 lowbit(3)=1 lowbit(4)=4 lowbit(5)=1 lowbit(6)=2 lowbit(7)=1 lowbit(8)=8 lowbit(9)=1 lowbit(10)=2 lowbit(11)=1 lowbit(12)=4 lowbit(13)=1 lowbit(14)=2 lowbit(15)=1 lowbit(16)=16 lowbit(17)=1 lowbit(18)=2 lowbit(19)=1 lowbit(20)=4 lowbit(21)=1 lowbit(22)=2 lowbit(23)=1 lowbit(24)=8 lowbit(25)=1 lowbit(26)=2 lowbit(27)=1 lowbit(28)=4 lowbit(29)=1 lowbit(30)=2 lowbit(31)=1 lowbit(32)=32 lowbit(33)=1 lowbit(34)=2 lowbit(35)=1 lowbit(36)=4 lowbit(37)=1 lowbit(38)=2 lowbit(39)=1 lowbit(40)=8 lowbit(41)=1 lowbit(42)=2 lowbit(43)=1 lowbit(44)=4 lowbit(45)=1 lowbit(46)=2 lowbit(47)=1 lowbit(48)=16 lowbit(49)=1 lowbit(50)=2 lowbit(51)=1 lowbit(52)=4 lowbit(53)=1 lowbit(54)=2 lowbit(55)=1 lowbit(56)=8 lowbit(57)=1 lowbit(58)=2 lowbit(59)=1 lowbit(60)=4 lowbit(61)=1 lowbit(62)=2 lowbit(63)=1 lowbit(64)=64
(2)修改
当我们修改A[i]的值时,可以从C[i]往根节点一路上溯,调整这条路上的所有C[]即可,对于节点i,父节点下标 p=i+lowbit(i)
代码实现: //增加某个元素的大小,给某个节点 i 加上 x update(int i,int x){ while(i<=n){ c[i]=c[i]+x; i=i+lowbit(i); } } (3)求数列的前n项和,只需找到n以前的所有最大子树,把其根节点的C加起来即可。 int Sum(int n) //求前n项的和. { int sum=0; while(n>0) { sum+=c[n]; n=n-lowbit(n); } return sum; } 例: public class TreeArray{ int n;//数组元素个数 int[] a;//原数组 int[] c;//对应的树状数组 public TreeArray(int[] a){ n=a.length; this.a=a; c=new int[a.length]; for(int i=1;i<a.length;i++){ for(int j=0;j<lowbit(i);j++) c[i]=c[i]+a[i-j]; } } private int lowbit(int t){//计算c[t]展开的项数 return t&(-t); } private void update(int i,int x){ while(i<=n){ c[i]=c[i]+x; i=i+lowbit(i); } } private int Sum(int k){ //求前k项的和. int sum=0; while(k>0){ sum+=c[k]; k=k-lowbit(k); } return sum; } public static void main(String args[]){ int a[]={0,1,2,3,4,5,6,7,8,9,10}; TreeArray ta=new TreeArray(a); System.out.println(ta.Sum(10)); ta.update(5,-20); System.out.println(ta.Sum(10)); System.out.println(ta.Sum(4)); } } 运行: C:\java>java TreeArray 55 35 10
发表评论
-
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2319北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1939import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1822POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1342接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2407当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1754关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1646关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1739关于树状数组,请参考:http://128kj.iteye.c ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2009POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2465设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2024继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2484继续上文http://128kj.iteye. ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2587先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2200一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 1996形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2773例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2052字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18542堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3973一、什么是并查集 ... -
根据二叉树前序遍历和中序遍历的结果输出后序遍历(java)
2012-10-07 19:58 3259前序遍历的第一个元素为根节点,在中序遍历中找到这个根节点 ...
相关推荐
树状数组 树状数组 树状数组 树状数组树状数组 树状数组 树状数组 树状数组树状数组 树状数组 树状数组 树状数组
树状数组 树状数组.ppt
洛谷上关于树状数组的一些简单例题,可参考学习,适合初学者
用java实现的树状数组,可以作为一个简单的模版来进行应用,如果有不懂得地方,可以上网查找树状数组的原理
树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现...
图文并茂的描述了树状数组的使用~~让大家详细了解梳妆数组的使用
树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3....
树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c...
树状数组详解
本文详细介绍了树状数组的原理,并用树状数组解校门外的树这个问题.
其实学树状数组说白了就是看那张图,那张树状数组和一般数组的关系的,看懂了基本就没问题了,推荐下面这个教程:http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
树状数组 后缀数组 字典树 多串匹配算法及启示
你知道树状数组吗,这是本人自己打的课件,希望你能喜欢,有区间求值单点修改,单点修改区间查询,区间修改区间查询,二维树状数组......
含义其实就是用一个数组,构成树形结构来维护原数组的前缀和。 显然,对于树状数组C,C[I]对应“管辖”多少个元素,与它对应二进制数最右端第一个1的位置有关。这样,就能够达到询问一个区间的值,或者改变值的时间...
数据结构基础之树状数组,有关其实现代码,及树状数组的建立和点的更新。
里面包含了树状数组算法的描述和代码实现 里面包含了树状数组算法的描述和代码实现 里面包含了树状数组算法的描述和代码实现
通过了解树状数组的原理和定义来解决有关给定一个由n个不同的整数组成的序列,最少需要交换多少次交换相邻的两个数,使其升序排列。
它是ACM中关于二维树状数组方面的资料。。
树状数组要开long double(运算过程会爆long long)
该PPT详细的写了树状数组的(二叉索引树)区间和查询以及应用