树状数组/二叉索引树（Binary Indexed Tree）：

A 数组就是原数组，C 数组则是树状数组。

二叉搜索树/二叉排序树（Binary Search Tree）：

1. 根的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
2. 根的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
3. 根的左、右子树也分别为二叉搜索树。

线段树/区间树（Segment tree）是一种二叉搜索树：

特点：

• 每个结点表示的是一个线段，或者说是一个区间。
• 当父节点的区间为$[x, y]$时，左孩子的区间就为$[x, \frac{ (x + y) }{ 2 }]$，右孩子的区间就为$[\frac{ (x + y) }{ 2 } + 1, y]$。
• 对于每一棵线段树上的节点，都有三个值：左区间、右区间以及权值。
  （在某些情况下只有左右区间，这个时候线段树只是作为维护某个值而使用的数据结构，如扫描线）

线段树主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为 O(logN）。而未优化的空间复杂度为 2N，因此有时需要离散化来压缩空间。

字典树/前缀树/单词查找树/键树（Trie）：

上图表示了关键字集合 {“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。

基本性质：

1. 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符互不相同。
4. 从第一字符开始有连续重复的字符只占用一个节点，比如上面的to，和ten，中重复的单词t只占用了一个节点。

应用：

1. 前缀匹配
2. 字符串检索
3. 词频统计
4. 字符串排序

数据结构与算法

1.数组、链表（单向、双向、双端）、栈和队列、二叉树、红黑树、哈希表、堆（最大和最小）、图

2.个人经验：栈和队列、哈希表、链表、二叉树的题较多，图的较少

3.查找：二分查找及其变形

4.二叉树：前序、中序、后序遍历，按规定方式打印，两个节点之间操作（最近公共祖先、距离）等问题。

5.最大堆和最小堆：大数量级数据找最大几个等问题、堆如何调整等问题。

6.图：深度优先、广度优先、单源最小路径Dijkstra，任意两点间最短路径Floyd-Warshall，最小生成树Prime和Kruskal

7.红黑树：特点及如何调整（基本上没人让你手撸红黑树）

8.栈和队列：经常作为算法题要用到的数据结构

8.八大排序：3个简单的：冒泡、选择、插入及其优化，5个高级的：快速排序、归并排序、堆排序、希尔排序、桶排序（快排、归并、堆很重要，经常手撸）

9.时间复杂度及空间复杂度分析

10.动态规划dp：这个比较难，背包问题之内的

推荐：数据结构C语言版（严蔚敏）、Java数据结构和算法（Robert Lafore）、剑指offer及leetcode刷题、大神可以看一下算法导论