1.树状数组(Binary Indexed Tree)

基于该数据结构的题目，一般具有明显的特征，也就是基于计算前缀和或者区间和。通常情况下，通过O(n^2)的算法可以实现功能，但是多数情况下都会超时，因此解决此类问题，需要设计或者依托更好的数据结构。一般情况下，关于树状数组和线段树的题目都属于较难的题目。

相关题目: 区域和检索-数组可修改，区域和检索-数组不可变，区间和的个数，翻转对，天际线问题

2.字典树(Trie树/前缀树)

经典题目，实现Trie树

#简化版的数据结构实现
class Trie():
    def __init__(self):
        self.holder = []
    def insert(self, word):
        self.holder.append(word)
    def search(self, word):
        return True if word in self.holder else False
    def startsWith(self, prefix):
        n = len(prefix)
        for word in self.holder:
            if word[:n] == prefix:
                return True
        return False

if __name__ == "__main__":
    trie = Trie()
    trie.insert("apple")
    assert(True == trie.search("apple"))
    assert(False == trie.search("app"))
    assert(True == trie.startsWith("app"))

有人认为：本质上是字典按照字母序迭代。

3.线段树

计算右侧小于当前元素的个数 截屏2022-11-11 11 17 47

4.并查集

并查集一般用于解决划分问题，围绕并查集的优化很多，维基百科就有很好的解释。涉及到的关键的两个操作:

（1）合并两个不相交集合

（2）判断两个元素是否属于同一集合

经典的题目是：朋友圈

5.跳表

跳表的C++实现