• 北京师范大学数学科学学院转专业考试. 2015年4月.

树状数组(binary indexed tree)能够高效地获取数组的子段和。 一般来说，树状数组可以用于解决数组子段和的动态查询或高效查询问题。

传统的数组单点修改的复杂度为\(~O(1)~\)，查询子段和的复杂度为\(~O(n)~\)。 而树状数组的修改和查询子段和复杂度均为\(~O(\log n)~\)。 所以在多组查询或动态查询时，用树状数组可以有效减小耗时，提高程序效率。

Treap是一种平衡二叉树，不过Treap会记录一个优先级（一般来说是随机生成），即Treap在以关键码构成二叉搜索树的同时，还会按照优先级的高低满足堆的性质，因此得名Treap（Tree + Heap）。 Treap不是二叉堆，二叉堆必须是完全二叉树，但Treap不必是。

对于每个结点，该结点的优先级不大于其所有孩子的优先级。Treap引入优先级的原因就是防止BST（二叉搜索树）退化成一条链，从而影响查询效率。

所以对于结点上的关键字来说，它是一颗BST，而对于结点上的优先级来讲，它是一个最小堆。其平均查找长度为\(~O(\log n)~\)。 Treap有插入、删除、旋转和查询等基本操作，进而可以实现查询第\(~k~\)大和查询关键字\(~x~\)排名等功能。

线段树是一颗完全二叉树，它的每个结点都表示一条线段，可以用来解决连续区间的动态查询问题． 线段树只支持区间信息可以由子区间信息合并而来的问题（如最值、乘积、区间和等）．

• 线段树的结构：一般来说，区间\(~[a,b]~\)的左儿子是\(~[a,m]~\)，右儿子是\(~[m+1,b]~\)；
• 线段树的空间：若数组长度是\(~N~\)，线段树需要的最大空间为\(~4N~\)；
• 线段树的效率：由于二叉树的性质，二叉树的操作时间复杂度基本保持在\(~O(\log N)~\)．

github + hexo 搭建个人网站详细过程.

本文针对的主要是Windows用户，不过总体步骤和Linux/Mac大同小异。