【数据结构2-1】二叉堆与树状数组

本章将介绍两种树形结构——二叉堆和树状数组。 大学生活是忙碌而丰富多彩的，有大量的任务需要完成，例如作业、实验、完成论文、兼职 工作等。这些任务都是不得不做的，而且每个任务都有对应的截止日期。对于一个有拖延症的学 生来说，他每次决定完成哪些任务，一定会选择最接近截止日期的任务，因为这个任务最为紧 迫，优先级最高。 对于这种可以查询最大或最小值，可以插入新的元素，可以删除最大最小值的集合容器，被 称为优先队列。通过使用二叉堆实现优先队列，可以较高效率地完成插入和查询操作。 而树状数组可以很方便的维护序列的前缀和等信息。因此，可以使用树状数组高效完成单点 修改、区间求和的任务。虽然之后介绍的线段树也可以完成这些任务，而且时间复杂度都是$O(logn)$，但是树状数组运行时间的常数更小，所需空间更小，代码也更加短小精悍。