[LeetCode]有趣的数据结构
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.线段树
4.并查集
并查集一般用于解决划分问题，围绕并查集的优化很多，维基百科就有很好的解释。涉及到的关键的两个操作:
（1）合并两个不相交集合
（2）判断两个元素是否属于同一集合
经典的题目是：朋友圈