数据结构学习路线总结与刷题建议
数据结构学习路线总结与刷题建议 写到这里，这套数据结构系列其实就到了一个很自然的收束点。前面一路从复杂度、递归、抽象数据类型出发，走过了线性结构、树、图、哈希、字符串、区间结构，再一路连到数据库、缓存...
标签：数据结构
数据结构与工程实践：数据库、缓存与搜索系统中的真实应用
数据结构与工程实践：数据库、缓存与搜索系统中的真实应用 学到这一篇，其实已经差不多把常见数据结构的地图走完了。这个时候如果还只是把它们分别记成： 数组一章； 链表一章； 树一章； 图一章； 哈希表一章...
并发相关结构：无锁队列与环形缓冲区
并发相关结构：无锁队列与环形缓冲区 前面的大多数数据结构默认都生活在一个相对“安静”的世界里： 只有一个执行流在操作它； 读写顺序清晰； 不会同时有多个线程抢着插入、删除和查询。 但真实系统里，大量高...
外部存储结构：外排序、倒排索引与 LSM Tree
外部存储结构：外排序、倒排索引与 LSM Tree 学了这么多数据结构之后，如果一直停留在“数据都能放进内存里”的想象里，视角其实还是不够完整。真实系统里，很多真正有挑战的问题，都发生在数据规模远超内...
Treap 与 Splay：随机平衡树与伸展树入门
Treap 与 Splay：随机平衡树与伸展树入门 在 BST、AVL 和红黑树之后，平衡查找树这条线其实还远没有结束。数据结构的有趣之处就在于：同样都是为了避免 BST 退化、维持对数级操作效率，人...
分块与莫队：离线区间问题的常见技巧
分块与莫队：离线区间问题的常见技巧 学到区间结构这里，很多人会自然把注意力放在线段树、树状数组这些“动态在线维护”结构上。但并不是所有区间问题都必须在线处理。有一类问题很有代表性： 所有查询在一开始就...
可持久化数据结构：版本化查询的基本思想
可持久化数据结构：版本化查询的基本思想 前面学树状数组和线段树时，我们默认一个非常自然的前提：每次更新之后，旧状态就被新状态覆盖了。也就是说，数据结构通常只有“当前版本”。 但现实中有很多问题并不满足...
线段树：区间查询与区间更新的核心结构
线段树：区间查询与区间更新的核心结构 如果说前缀和适合静态区间和，树状数组适合“单点更新 + 前缀 / 区间查询”，那么当问题进一步升级成： 区间查询更复杂； 区间更新也很频繁； 还可能维护最大值、最...
树状数组：高效处理前缀和与单点更新
树状数组：高效处理前缀和与单点更新 前缀和很强，但它有一个明显短板：一旦数组中的元素频繁变化，整张前缀和表维护起来就会很痛苦。也就是说，前缀和非常适合“静态多查询”，却不太适合“动态单点更新 + 区间...
区间类结构基础：前缀和与差分
区间类结构基础：前缀和与差分 学到这里，很多数据结构都在围绕“单点操作”展开：查一个值、插一个点、删一个节点、维护一个最值。但在很多实际问题里，我们关心的并不是单个位置，而是一整段区间。例如： 某个区...