写在前面：关于这份计算机组成原理学习总结
写在前面：关于这份计算机组成原理学习总结 很多人第一次接触计算机组成原理时，都会有一种很强的割裂感：一边知道自己每天都在写代码、跑程序、调接口，另一边又看到寄存器、加法器、总线、时钟周期、Cache、流水线这些看起来很“硬”的概念，于是很容...
数据结构学习路线总结与刷题建议
数据结构学习路线总结与刷题建议 写到这里，这套数据结构系列其实就到了一个很自然的收束点。前面一路从复杂度、递归、抽象数据类型出发，走过了线性结构、树、图、哈希、字符串、区间结构，再一路连到数据库、缓存、搜索系统中的真实应用。如果只是把这些内...
数据结构与工程实践：数据库、缓存与搜索系统中的真实应用
数据结构与工程实践：数据库、缓存与搜索系统中的真实应用 学到这一篇，其实已经差不多把常见数据结构的地图走完了。这个时候如果还只是把它们分别记成： 数组一章； 链表一章； 树一章； 图一章； 哈希表一章； 那理解其实还是偏“课本化”的。真正有...
并发相关结构：无锁队列与环形缓冲区
并发相关结构：无锁队列与环形缓冲区 前面的大多数数据结构默认都生活在一个相对“安静”的世界里： 只有一个执行流在操作它； 读写顺序清晰； 不会同时有多个线程抢着插入、删除和查询。 但真实系统里，大量高性能服务都处在并发环境下。这时候，问题就...
外部存储结构：外排序、倒排索引与 LSM Tree
外部存储结构：外排序、倒排索引与 LSM Tree 学了这么多数据结构之后，如果一直停留在“数据都能放进内存里”的想象里，视角其实还是不够完整。真实系统里，很多真正有挑战的问题，都发生在数据规模远超内存的时候： 日志量特别大； 索引体积很大...
Treap 与 Splay：随机平衡树与伸展树入门
Treap 与 Splay：随机平衡树与伸展树入门 在 BST、AVL 和红黑树之后，平衡查找树这条线其实还远没有结束。数据结构的有趣之处就在于：同样都是为了避免 BST 退化、维持对数级操作效率，人们并没有只发明一种平衡方法，而是不断尝试...
分块与莫队：离线区间问题的常见技巧
分块与莫队：离线区间问题的常见技巧 学到区间结构这里，很多人会自然把注意力放在线段树、树状数组这些“动态在线维护”结构上。但并不是所有区间问题都必须在线处理。有一类问题很有代表性： 所有查询在一开始就已经给出； 不一定要求实时回答； 重点在...
可持久化数据结构：版本化查询的基本思想
可持久化数据结构：版本化查询的基本思想 前面学树状数组和线段树时，我们默认一个非常自然的前提：每次更新之后，旧状态就被新状态覆盖了。也就是说，数据结构通常只有“当前版本”。 但现实中有很多问题并不满足这个前提。你可能会想： 我想查询某次修改...
线段树：区间查询与区间更新的核心结构
线段树：区间查询与区间更新的核心结构 如果说前缀和适合静态区间和，树状数组适合“单点更新 + 前缀 / 区间查询”，那么当问题进一步升级成： 区间查询更复杂； 区间更新也很频繁； 还可能维护最大值、最小值、区间和、区间最值等多种信息； 这时...
树状数组：高效处理前缀和与单点更新
树状数组：高效处理前缀和与单点更新 前缀和很强，但它有一个明显短板：一旦数组中的元素频繁变化，整张前缀和表维护起来就会很痛苦。也就是说，前缀和非常适合“静态多查询”，却不太适合“动态单点更新 + 区间查询”。 树状数组，通常也叫 Fenwi...