树状数组:是一个查询和修改复杂度都为log(n)的数据结构,假设数组A[1..n],那么查询A[1]+...+A[n]的时,间是log级别的,而且是一个在线的数据结构。
树状数组原理如下:主要是依靠神奇的二进制转换进行保存数据。所以我们需要使用lowbit函数。
const int D = 1000005;
int s[D];
inline int lowbit(int x) {
return x & (-x);
}//用lowbit函数算出该数在二进制下的最后一个1的位置;
void add(int x, int w) {
while (x < D) {
s[x] += w;
x += lowbit(x);
}
}//修改树状数组中的元素:并且每次仅对x进行+lowbit的处理,如图所示,即修改了一个节点之后,只需要对在它的上层的全部节点进行修改,而不需要全程遍历修改,因而复杂度取决于二进制中的最大位数。
细节:如图,2节点存储了1节点的数据,即包含了2节点之前的全部数据和,4节点存储了3节点的数据和2节点的数据,即包含了4节点之前的全部数据和,6节点储存了5节点的数据,8节点储存了7节点和6节点的数据和4节点和2节点的数据,即代表了8节点之前的全部数据和。
int sum(int x) {
int ret = 0;
while (x > 0) {
ret += s[x];
x -= lowbit(x);
}
return ret;
}//计算前缀和的函数,为什么可以每次直接减少一个lowbit,证明如下:对于区间[x - lowbit + 1, x];
//设x为A1B,其中A为一窜二进制,B为B个0;
//那么,x - lowbit + 1就等于AB1,(当AB1不断进行+lowbit即可以得到A0B即x,此处先写出这个关系,方便后文阐述)即区间[AB1, A0B]之间的和可以只用A0B一个节点来表示,继续来看为什么,在add函数中,每当对该区间的任个数进行赋值或修改时,不断进行+lowbit最后都会对x即A1B进行赋值或修改,因此,x这个节点包含了这个区间内所有节点的修改结果,是最终结果的集合体。
因此,通过在add中进行赋值的顺序,我们可以看出,在sum函数中,要求前缀和,只需每次对该节点进行-lowbit即可,这样的复杂度仅仅取决于二进制中1的最多个数。
//另外还可以这样看:设原数组为A[1..N],树状数组为c[1..N],其中c[k] = A[k - lowbit + 1] + ... + A[k]。比如c[6] = A[5] + A[6]。
假设 A为被计数数组,C为树状数组(计数)
0000 0001:C1 = A1
0000 0010:C2 = A1 + A2
0000 0011:C3 = A3
0000 0100:C4 = A1 + A2 + A3 + A4
0000 0101:C5 = A5
0000 0110:C6 = A5 + A6
0000 0111:C7 = A7
0000 1000:C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
...
0001 0000:C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8+ A9 + A10 + A11 + A12 + A13 + A14 + A15+ A16
- 大小: 82.7 KB
分享到:
相关推荐
初识数组(Java) 第一回数组的概念数组的特点数组的初始化方式数组的使用 数组的概念 数组的概念:是一种容器,可以同时存放多个数据值; 数组的特点 数组的特点: 数组是一种引用数据类型; 数组当中的多个数据,...
java第四章数组初识排序
java语言中,数组是一种最简单的复合数据类型。数组是有序数据的集合,数组中的每个元素具有相同的数据类型,可以用一个统一的数组名和下标来唯一地确定数组中的元素。数组有一维数组和多维数组。
初识C++ 初识C++ 初识C++初识C++初识C++初识C++初识C++
1运算符和表达式 C语言运算符是说明特定操作的符号,它是构造C语言表达式的工具。C语言的运算异常丰富,除了控制语句和输入输出以外的几乎所有的基本操作都作为运算符处理。除了常见的三大类,算术运算符、关系...
初识云计算初识云计算初识云计算初识云计算初识云计算初识云计算初识云计算初识云计算
c语言学习第五天作业和思维导图笔记,冒泡排序算法,初识字符数组。
初识计算机初识计算机初识计算机
python 列表初识,通过此代码,你能够了解到python的列表操作
初识计算机PPT课件.pptx
jvm初识及JIT优化jvm初识及JIT优化jvm初识及JIT优化jvm初识及JIT优化jvm初识及JIT优化jvm初识及JIT优化jvm初识及JIT优化jvm初识及JIT优化jvm初识及JIT优化jvm初识及JIT优化jvm初识及JIT优化jvm初识及JIT优化jvm初识...
初识数组 概念: 数组就是一个可以存储一组或一系列数值的变量 数组组成: 数组是由一个或多个数组元素组成的 数组元素: 一每个数组由键(Key)和值(Value)构成 键: “键”为元素的是被名称,也被称为数组...
初识计算机 幼儿园计算机课程《初识计算机》全文共15页,当前为第1页。 1. 计算机发展过程 结绳记事 算筹 幼儿园计算机课程《初识计算机》全文共15页,当前为第2页。 1. 计算机发展过程 珠算 幼儿园计算机课程《初识...
三年级信息技术课程《初识画图》课件内容 因为要参加比赛,所属机房 装不上
初识JavaScript(源代码)初识JavaScript(源代码)初识JavaScript(源代码)初识JavaScript(源代码)初识JavaScript(源代码)初识JavaScript(源代码)初识JavaScript(源代码)初识JavaScript(源代码)初识...
Java元码,直接可以打开。一个小小的程序,这是我初识Java后自己做的,
本课是初中信息技术初识excel的教学设计
初识C语言.pdf
目录 PAGE 3 第1章 初识Python 第2章 基本数据类型 第3章 Python的流程控制 第4章 数组操作 第5章 文件操作 第6章 绘制需要的图表 第7章 函数 第8章 面向对象 第9章 异常 第10章 集合与概率 第11章 学点统计学 第12...
初识Python 少儿编程python教案——初识Python全文共24页,当前为第1页。 Python基本概念 海龟编辑器 绘图准备 课程知识点 使用画笔 少儿编程python教案——初识Python全文共24页,当前为第2页。 Python基本概念 ...