tag: %u6570%u636E%u7ED3%u6784.md

Tag: 数据结构

8 posts
链表核心操作

链表所有错都从一句话来:cur.next 之前,先把 cur.next 存下来,否则后面那一截就丢了。记住这句,再配 dummy / 双指针 / 头插反转三招,80% 链表题就是模板题。

...
堆 / 优先队列

一句话:堆是用数组下标隐式表达的完全二叉树。看着是树,内存是平的。每次 O(log n) 拿到当前最值,建堆只要 O(n)。

...
哈希表 Hash Table

哈希表本质不是数据结构,是一种算法套路:用 O(1) 查询换 O(N) 遍历。看到”找两个元素满足某关系”就该条件反射。

...
差分数组与前缀和

差分数组 = 前缀和的逆运算。区间 [l, r] += k 这种 的活,改成两次单点改 diff[l] += k; diff[r+1] -= k, 搞定。最后再做一遍前缀和还原。记住这一句,这辈子的区间批量加都不会再写循环。

...
Trie 前缀树

每个节点存一个字符,从根到叶的路径就是一个完整字符串。共同前缀的字符串共用前面的节点 — 这就是为什么叫”前缀树”。插入/查询都是 ,跟字典里有多少词无关。

...
并查集

每个集合用一棵树,根是集合的代表。find 沿父指针往上爬到根,union 把一个根挂到另一个根下。加上路径压缩和按秩合并,单次操作均摊 — 反阿克曼函数,实际 ,基本就是

...
树状数组
树状数组,也称为二进制索引树,是一种支持单点更新和区间查询的数据结构。在大多数情况下,我们可以用它来查询区间和、区间乘积或其他满足以下条件的操作: 结合律: 具有逆运算,我们可以通过 和 推断出 它基于这样一个假设:任何前缀 都可以分解为最多 个区间,这些区间的信息是已知的。 从上图可以看出,每个位置 控制的区间的右边界是 。在树状数组中, 被分配控制长度为 的区间。这里, ...
线段树
线段树是一种常用于维护区间信息的数据结构。 线段树可以在 的时间复杂度内执行诸如单点更新、区间更新和区间查询(区间和、区间最大值、区间最小值)等操作。 ...