- 北京师范大学数学科学学院转专业考试. 2015年4月.
数据结构——树状数组 Binary Indexed Tree
发表于
|
分类于
学习
树状数组(binary indexed tree)能够高效地获取数组的子段和。 一般来说,树状数组可以用于解决数组子段和的动态查询或高效查询问题。
传统的数组单点修改的复杂度为\(~O(1)~\),查询子段和的复杂度为\(~O(n)~\)。 而树状数组的修改和查询子段和复杂度均为\(~O(\log n)~\)。 所以在多组查询或动态查询时,用树状数组可以有效减小耗时,提高程序效率。
数据结构——平衡树 Treap
发表于
|
分类于
学习
Treap是一种平衡二叉树,不过Treap会记录一个优先级(一般来说是随机生成),即Treap在以关键码构成二叉搜索树的同时,还会按照优先级的高低满足堆的性质,因此得名Treap(Tree + Heap)。 Treap不是二叉堆,二叉堆必须是完全二叉树,但Treap不必是。
对于每个结点,该结点的优先级不大于其所有孩子的优先级。Treap引入优先级的原因就是防止BST(二叉搜索树)退化成一条链,从而影响查询效率。
所以对于结点上的关键字来说,它是一颗BST,而对于结点上的优先级来讲,它是一个最小堆。其平均查找长度为\(~O(\log n)~\)。 Treap有插入、删除、旋转和查询等基本操作,进而可以实现查询第\(~k~\)大和查询关键字\(~x~\)排名等功能。
数据结构——线段树 Segment Tree
发表于
|
分类于
学习
线段树是一颗完全二叉树,它的每个结点都表示一条线段,可以用来解决连续区间的动态查询问题. 线段树只支持区间信息可以由子区间信息合并而来的问题(如最值、乘积、区间和等).
- 线段树的结构:一般来说,区间\(~[a,b]~\)的左儿子是\(~[a,m]~\),右儿子是\(~[m+1,b]~\);
- 线段树的空间:若数组长度是\(~N~\),线段树需要的最大空间为\(~4N~\);
- 线段树的效率:由于二叉树的性质,二叉树的操作时间复杂度基本保持在\(~O(\log N)~\).