例题分析
LeetCode 第 212 题：给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
说明：你可以假设所有输入都由小写字母 a-z 组成。
解题思路
这是一道出现较为频繁的难题，题目给出了一个二维的字符矩阵，然后还给出了一个字典，现在要求在这个字符矩阵中找到出现在字典里的单词。
由于字符矩阵的每个点都能作为一个字符串的开头，所以必须得尝试从矩阵中的所有字符出发，上下左右一步步地走，然后去和字典进行匹配，如果发现那些经过的字符能组成字典里的单词，就把它记录下来。
可以借用深度优先的算法来实现（关于深度优先算法，将在第 06 节课深入探讨），如果你对它不熟悉，可以把它想象成走迷宫。
字典匹配的解法 1：每次都循环遍历字典，看看是否存在字典里面，如果把输入的字典变为哈希集合的话，似乎只需要 O(1) 的时间就能完成匹配。
但是，这样并不能进行前缀的对比，即，必须每次都要进行一次全面的深度优先搜索，或者搜索的长度为字典里最长的字符串长度，这样还是不够高效。
字典匹配的解法 2：对比字符串的前缀，借助前缀树来重新构建字典。
假如在矩阵里遇到了一个字符”V”，而字典里根本就没有以“V”开头的字符串，则不需要将深度优先搜索进行下去，可以大大地提高搜索效率。
构建好了前缀树之后，每次从矩阵里的某个字符出发进行搜索的时候，同步地对前缀树进行对比，如果发现字符一直能被找到，就继续进行下去，一步一步地匹配，直到在前缀树里发现一个完整的字符串，把它输出即可。
线段树（Segment Tree）
举例：假设有一个数组 array[0 … n-1]， 里面有 n 个元素，现在要经常对这个数组做两件事。
更新数组元素的数值
求数组任意一段区间里元素的总和（或者平均值）
解法 1：遍历一遍数组。
时间复杂度 O(n)。
解法 2：线段树。
- 线段树，就是一种按照二叉树的形式存储数据的结构，每个节点保存的都是数组里某一段的总和。
- 适用于数据很多，而且需要频繁更新并求和的操作。
- 时间复杂度 O(logn)。
实现
举例：数组是 [1, 3, 5, 7, 9, 11]，那么它的线段树如下。
根节点保存的是从下标 0 到下标 5 的所有元素的总和，即 36。左右两个子节点分别保存左右两半元素的总和。按照这样的逻辑不断地切分下去，最终的叶子节点保存的就是每个元素的数值。
解法：
1. 更新数组里某个元素的数值
从线段树的根节点出发，更新节点的数值，它保存的是数组元素的总和。修改的元素有可能会落在线段树里一些区间里，至少叶子节点是肯定需要更新的，所以，要做的是从根节点往下，判断元素的下标是否在左边还是右边，然后更新分支里的节点大小。因此，复杂度就是遍历树的高度，即 O(logn)。
2. 对数组某个区间段里的元素进行求和
方法和更新操作类似，首先从根节点出发，判断所求的区间是否落在节点所代表的区间中。如果所要求的区间完全包含了节点所代表的区间，那么就得加上该节点的数值，意味着该节点所记录的区间总和只是所要求解总和的一部分。接下来，不断地往下寻找其他的子区间，最终得出所要求的总和。
建议：线段树的实现书写起来有些繁琐，需要不断地练习。
例题分析
LeetCode 第 315 题：给定一个整数数组 nums，按要求返回一个新数组 counts，使得数组 counts 有该性质——counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例
输入：[5, 2, 6, 1]
输出：[2, 1, 1, 0]
解释
5 的右侧有 2 个更小的元素（2 和 1）
2 的右侧仅有 1 个更小的元素（1）
6 的右侧有 1 个更小的元素（1）
1 的右侧有 0 个更小的元素
解题思路
给定一个数组 nums，里面都是一些整数，现在要求打印输出一个新的数组 counts，counts 数组的每个元素 counts[i] 表示 nums 中第 i 个元素右边有多少个数小于 nums[i]。
例如，输入数组是 [5, 2, 6, 1]，应该输出的结果是 [2, 1, 1, 0]。
因为，对于 5，右边有两个数比它小，分别是 2 和 1，所以输出的结果中，第一个元素是 2；对于 2，右边只有 1 比它小，所以第二个元素是 1，类推。
如果使用线段树解法，需要理清线段树的每个节点应该需要包含什么样的信息。
线段树每个节点记录的区间是数组下标所形成的区间，然而对于这道题，因为要统计的是比某个数还要小的数的总和，如果把分段的区间设计成按照数值的大小来划分，并记录下在这个区间中的数的总和，就能快速地知道比当前数还要小的数有多少个。
1. 首先，让从线段树的根节点开始，根节点记录的是数组里最小值到最大值之间的所有元素的总和，然后分割根节点成左区间和右区间，不断地分割下去。
2. 初始化，每个节点记录的在此区间内的元素数量是 0，接下来从数组的最后一位开始往前遍历，每次遍历，判断这个数落在哪个区间，那么那个区间的数量加一。
3. 遇到 1，把它加入到线段树里，此时线段树里各个节点所统计的数量会发生变化。
4. 当前所遇到的最小值就是 1。
5. 把 6 加入到线段树里。
6. 求比 6 小的数有多少个，即查询线段树，从 1 到 5 之间有多少个数。
7. 从根节点开始查询。由于所要查询的区间是 1 到 5，无法包含根节点的区间 1 到 6，所以继续往下查询。
8. 左边，区间 1 到 3 被完全包含在 1 到 5 之间，把该节点所统计好的数返回。
9. 右边，区间 1 到 5 跟区间 4 到 6 有交叉，继续往下看，区间 4 到 5 完全被包含在 1 到 5 之间，所以可以马上返回，并把统计的数量相加。
10. 最后得出，在当前位置，在 6 的右边比 6 小的数只有一个。
通过这样的方法，每次把当前的数用线段树进行个数统计，然后再计算出比它小的数即可。算法复杂度是 O(nlogn)。
树状数组（Fenwick Tree / Binary Indexed Tree）
实现
举例：假设有一个数组 array[0 … n-1]， 里面有 n 个元素，现在要经常对这个数组做两件事。
- 更新数组元素的数值
- 求数组前 k 个元素的总和（或者平均值）
解法 1：线段树。
线段树能在 O(logn) 的时间里更新和求解前 k 个元素的总和。
解法 2：树状数组。
该问题只要求求解前 k 个元素的总和，并不要求任意一个区间。
树状数组可以在 O(logn) 的时间里完成上述的操作。
相对于线段树的实现，树状数组显得更简单。
特点
树状数组的数据结构有以下几个重要的基本特征。
它是利用数组来表示多叉树的结构，在这一点上和优先队列有些类似，只不过，优先队列是用数组来表示完全二叉树，而树状数组是多叉树。
树状数组的第一个元素是空节点。
如果节点 tree[y] 是 tree[x] 的父节点，那么需要满足条件：y = x - (x & (-x))。
建议：由于树状数组所解决的问题跟线段树有些类似，所以不花篇幅进行问题的讨论。LeetCode 上有很多经典的题目可以用树状数组来解决，比如 LeetCode 第 308 题，求一个动态变化的二维矩阵里，任意子矩阵里的数的总和。
总结
这节课讲解了一些高级的数据结构。
1. 优先队列
经常出现在考题里的，它的实现过程比较繁琐，但是很多编程语言里都有它的实现，所以在解决面试中的问题时，实行“拿来主义”即可。
鼓励你自己练习实现一个优先队列，在实现它的过程中更好地去了解它的结构和特点。
2. 图
被广泛运用的数据结构，很多涉及大数据的问题都得运用到图论的知识。
比如在社交网络里，每个人可以用图的顶点表示，人与人直接的关系可以用图的边表示；再比如，在地图上，要求解从起始点到目的地，如何行驶会更快捷，需要运用图论里的最短路径算法。
3. 前缀树
出现在许多面试的难题当中。
因为很多时候你得自己实现一棵前缀树，所以你要能熟练地书写它的实现以及运用它。
4. 线段树和树状数组
应用场合比较明确。
例如，问题变为在一幅图片当中修改像素的颜色，然后求解任意矩形区间的灰度平均值，那么可以考虑采用二维的线段树了。
建议：LeetCode 平台上，针对上面的这些高级数据结构都有丰富的题目，希望你能用功学习。
