据结构在ACM中应用非常广泛，但单独考查某个数据结构基础的题目较少，一般都是起一些辅助的作用，比如我们前面提到的优先队列，还有一个非常常用的就是哈希，前面我们提到过，在BFS的过程中，我们需要从每次扩展出来的点中筛选出来我们需要的点放入队列中，哪些是不需要的点，一般来说，指的是和以前某个搜索过的点具有相同的状态的点，而判别状态是否相同的方法经常是利用哈希来保存以前搜索过的状态，并且判断每次扩展出来的点的状态是否已经存在，如果不存在，我们再把它放入队列中。7数据结构之提高篇包括并查集树状数组线段树数据结构还有一些相对来说比较高级的应用，这些知识点可能会作为一个知识点单独考查，首先是并查集，并查集的基本思想是在一个集合中选出一个元素作为一个集合代表元素，通过对这些代表元素的操作来实现集合之间的合并操作，在求最小生成树的经典算法Kruscal中也会用到并查集来判断两个元素是否属于同一条边，这在下一部分图论的总结中会提到。并查集也有很多的题目可以做，经典题有食物链，搞同性恋的虫子，帮派结伙等，并查集还有一个变型就是从一个集合中删除某一个元素，我们知道，普通的并查集是不包括删除元素
f的功能的，而删除元素的实现其实也很简单，就是对每个点都建立一个索引，一开始每个点的索引都指向自己，当一个元素被删除掉的时候，先建立一个新的不属于任何集合的新点，在把被删除掉的点索引到那个新点之上即可。第二部分是树状数组，他支持在O
log
的复杂度内算出区间内的元素之和，他的思想很是巧妙，就是树状数组总
结：假设c为树状数组，a为原数组，则两者之间存在这么一个关系，ci代表的意义是从ai开始往前2k个元素的和k为i化成二进制后尾部包含的0的个数。由位运算的性质可以得到：对于i来说，ii2k，那么树状数组的基本功能就能明白了。树状数组也有比较多的题，PKU_1990，PKU_2828，PKU_2155等等。最后我想说一下线段树，线段树是一个非常强大的数据结构，他支持在O
log
的复杂度内对区间范围内的元素进行修改，删除等操作，和并查集，树状数组不同的是，线段树的实现非常灵活，一道题一个样，几乎没有什么定式，当然了，最为基本的思想就是每个节点代表一个区间，他的左右子树分别为左半区间和右半区间，如此这般地递归定义，直到为
一个点或者包含一个单位为止。线段树也有几个基本模型和经典例题，首先我想讲的是线段树的一种相对而言比较简单但是非常经r