Bit
时代内涵，始终注重培养学生实事求是的科学态度、团结勤奋的工作作风、求实创新的精神品格，培养和造就了一大批素质优良的毕业生。建校69年来，共培养毕业生14.2万余人，产生了17名院士、65名省部级以上党政领导干部和40余名将军。多年来，广大北理工校友秉承学校的优良传统，为经济社会建设和国防科技工业发展作出了卓越贡献。
基本思想是：将原数据划分为多个区间，当要查询或更新某个数或某段数据时，只需更新到各个区间不必细化到具体的各个元素
例有k个元素的集合，划分区间时利用函数
int lowbit(int x){
return x&(x^(x–1));（或return x&(-x);）
}
求得各个区间的范围
树状数组是一个查询和修改复杂度都为log(n)的数据结构，假设数a[1..n]，那么查询a[1]+...+a[n]的时间是log级别的，而且是一个在线的数据结构，
支持随时修改某个元素的值，复杂度也为log级别。
来观察这个图：
令这棵树的结点编号为C1，C2...Cn。令每个结点的值为这棵树的值的总和，那么容易发现：
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
这里有一个有趣的性质：
设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必然为Ax，
所以很明显：Cn = A(n – 2^k + 1) + ... + An
算这个2^k有一个快捷的办法，定义一个函数如下即可：
int lowbit(int x){
return x&(x^(x–1));（或return x&(-x);）}
当想要查询一个SUM(n)时，可以依据如下算法即可：
step1: 令sum = 0，转第二步；
step2: 假如n <= 0，算法结束，返回sum值，否则sum = sum + Cn，转第三步；
step3: 令n = n – lowbit(n)，转第二步。
可以看出，这个算法就是将这一个个区间的和全部加起来，为什么是效率是log(n)的呢？以下给出证明：
n = n – lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。
那么修改呢，修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log(n)的祖先。
所以修改算法如下（给某个结点i加上x）：
step1: 当i > n时，算法结束，否则转第二步；
step2: Ci = Ci + x， i = i + lowbit(i)转第一步。
i = i +lowbit(i)这个过程实际上也只是一个把末尾1补为0的过程。
对于数组求和来说树状数组简直太快了!
算法分析:
如果直接做的话,修改的复杂度是O(1),询问的复杂度是O(N),M次询问的复杂度是M*N.M,N的范围可以有100000以上,所以这样做会超时,但是如果用线段树的话,还是很不错的!
BIT
工业技术学士 Bachelor of Industrial Technology 的英文缩写。
Bit
一般是说明传感器的信号有几个BIT,是个计量单位。
Bit
化学里，一种优良的杀菌剂，稳定，优异的热稳定性，常常用于其他防腐剂不起作用的高温，强碱环境，与
大多数原料有良好的配伍性。
化学名字： 1，2苯并异噻唑-3-酮
一般溶液为此化学物质的乙二醇溶液20%含量。
bit中文名称是位，音译“比特”，是用以描述电脑数据量的最小单位。
二进制数系统中，每个0或1就是一个位(bit)。
bit 来自binary digit (二进制数字)
有以下用途：数据率---就是数据的传输速率，单位是：比特/秒（意思是每秒传送多少二进制数字《1或0》）
通常记为： bit/s b/s Kb/s Mb/s Gb/s Tb/s bps(bit per second)而这几个英文字母的来源：K:kilo(千) M:mega(兆) G:giga(吉) T:tera(太)
单位换算
1Byte=8bit
1KB=1024Byte(字节)=8*1024bit
1MB=1024KB
1GB=1024MB
1TB=1024GB
BIT （Binary Indexed Tree）树状数组
基本思想是：将原数据划分为多个区间，当要查询或更新某个数或某段数据时，只需更新到各个区间不必细化到具体的各个元素例有k个元素的集合，划分区间时利用函数
int lowbit(int x){
return x&(x^(x–1));（或return x&(-x);）
}
求得各个区间的范围
树状数组是一个查询和修改复杂度都为log(n)的数据结构，假设数a[1..n]，那么查询a[1]+...+a[n]的时间是log级别的，而且是一个在线的数据结构，
支持随时修改某个元素的值，复杂度也为log级别。
来观察这个图：
令这棵树的结点编号为C1，C2...Cn。令每个结点的值为这棵树的值的总和，那么容易发现：
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
这里有一个有趣的性质：
设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必然为Ax，
所以很明显：Cn = A(n – 2^k + 1) + ... + An
算这个2^k有一个快捷的办法，定义一个函数如下即可：
int lowbit(int x){
return x&(x^(x–1));（或return x&(-x);）}
当想要查询一个SUM(n)时，可以依据如下算法即可：
step1: 令sum = 0，转第二步；
step2: 假如n <= 0，算法结束，返回sum值，否则sum = sum + Cn，转第三步；
step3: 令n = n – lowbit(n)，转第二步。
可以看出，这个算法就是将这一个个区间的和全部加起来，为什么是效率是log(n)的呢？以下给出证明：
n = n – lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。
那么修改呢，修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log(n)的祖先。
所以修改算法如下（给某个结点i加上x）：
step1: 当i > n时，算法结束，否则转第二步；
step2: Ci = Ci + x， i = i + lowbit(i)转第一步。
i = i +lowbit(i)这个过程实际上也只是一个把末尾1补为0的过程。
对于数组求和来说树状数组简直太快了!
算法分析:
如果直接做的话,修改的复杂度是O(1),询问的复杂度是O(N),M次询问的复杂度是M*N.M,N的范围可以有100000以上,所以这样做会超时,但是如果用线段树的话,还是很不错的!
BIT的其它含义
BIT工业技术学士 Bachelor of Industrial Technology 的英文缩写。
Bit
一般是说明传感器的信号有几个BIT,是个计量单位。
Bit
化学里，一种优良的杀菌剂，稳定，优异的热稳定性，常常用于其他防腐剂不起作用的高温，强碱环境，与
大多数原料有良好的配伍性。
化学名字： 1，2苯并异噻唑-3-酮
一般溶液为此化学物质的乙二醇溶液20%含量。
bit中文名称是位，音译“比特”，是用以描述电脑数据量的最小单位。
二进制数系统中，每个0或1就是一个位(bit)。
bit 来自binary digit (二进制数字)
有以下用途：数据率---就是数据的传输速率，单位是：比特/秒（意思是每秒传送多少二进制数字《1或0》）
通常记为： bit/s b/s Kb/s Mb/s Gb/s Tb/s bps(bit per second)而这几个英文字母的来源：K:kilo(千) M:mega(兆) G:giga(吉) T:tera(太)
单位换算
1Byte=8bit
1KB=1024Byte(字节)=8*1024bit
1MB=1024KB
1GB=1024MB
1TB=1024GB
上一篇：中国地质大学地球科学学院[ 03-17 ]
下一篇：广东商学院[ 03-17 ]
