第一周(04.01 - 04.07)

本周主要学习了数据结构的内容

具体包括：优先队列、并查集、树状数组

优先队列通过LA3135、Uva11997两道例题来进行练习，通过优先队列学习了多路归并的问题，多路归并就是k个有序表合成一个有序表（假设每个表都是生序排列的）用优先队列去维护每个表的当前元素，则时间复杂度为O(nlogk).

并查集通过LA3644、La3027两道例题来进行练习,并查集关键在于路经压缩，为了加快查找速度，查找时将x到根节点路径上的所有点的pre（上级）设为根节点，该优化方法称为压缩路径。使用该优化后，平均复杂度可视为Ackerman函数的反函数，实际应用中可粗略认为其是一个常数。

树状数组

核心思想在于

C[i]=A[i-2^k+1]+A[i-2^k+2]+......A[i];

C[i]=A[i-lowbit(i)+1]+A[i-lowbit(i)+2]+......A[i];

通过x&(-x)快速算出最低位的1

建树时复杂度为nlogn 不过求连续和为logn 

第二周（04.08-04.14）

1.线段树，是一种二叉搜索树。它将一段区间划分为若干单位区间，每一个节点都储存着一个区间。它功能强大，支持区间求和，区间最大值，区间修改，单点修改等操作。

线段树的思想和分治思想很相像。

线段树的每一个节点都储存着一段区间[L…R]的信息，其中叶子节点L=R。它的大致思想是：将一段大区间平均地划分成2个小区间，每一个小区间都再平均分成2个更小区间……以此类推，直到每一个区间的L等于R（这样这个区间仅包含一个节点的信息，无法被划分）。通过对这些区间进行修改、查询，来实现对大区间的修改、查询。

这样一来，每一次修改、查询的时间复杂度都只为O(log2n) O(\log_2n)O(log2n)。

但是，可以用线段树维护的问题必须满足区间加法，否则是不可能将大问题划分成子问题来解决的。

难点区间修改：

懒惰标记

标记的含义：本区间已经被更新过了，但是子区间却没有被更新过，被更新的信息是什么（区间求和只用记录有没有被访问过，而区间加减乘除等多种操作的问题则要记录进行的是哪一种操作）

2.字典树，又称为单词查找树，Tire数，是一种树形结构，它是一种哈希树的变种。

根节点不包含字符，除根节点外的每一个子节点都包含一个字符

从根节点到某一节点。路径上经过的字符连接起来，就是该节点对应的字符串

每个节点的所有子节点包含的字符都不相同

优点：利用字符串的公共前缀来减少查询时间，最大限度的减少无谓的字符串比较，查询效率比哈希树高。

第三周（04.15-04.21）