MMrHeinxiaoh.hashnode.dev·Oct 4, 2025 · 9 min read字典树和后缀数组14.2 字典树的应用算法设计 字典树，也叫Trie树或者前缀树，顾名思义，它就是一种专门用来处理字符串前缀的树形结构。每个节点代表一个字符，从根节点到任意一个节点的路径，就构成了一个字符串。它的核心思想就是用空间换时间，利用字符串的公共前缀来降低查询时间的开销。 14.2.1 实现Trie（前缀树） 问题描述 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。 Trie() 初始化前缀树对象。 void insert(String...00
MMrHeinxiaoh.hashnode.dev·Oct 4, 2025 · 10 min read树状数组（ Binary Indexed Tree）树状数组（Fenwick Tree / Binary Indexed Tree）这个东西。这玩意儿听起来挺唬人，但本质上就是个用数组模拟树形结构的工具，专门用来解决一类问题：频繁的单点更新和区间查询。如果我们用普通数组，更新是 O(1)，但查区间和就是 O(N)；用前缀和数组，查区间和是 O(1)，但你更新一个点，后面所有的前缀和都得改，又是 O(N)。两边都不讨好。树状数组就把这两个操作都干到了 O(logN)，一下就平衡了。 废话不多说，咱们从题入手，看看这东西到底怎么用，思路是怎么一步步升...00
MMrHeinxiaoh.hashnode.dev·Oct 4, 2025 · 9 min read线段树-树形结构线段树，顾名思义，就是用来处理区间或线段问题的树形结构。它能高效地解决一类问题：对一个数组进行频繁的区间查询和元素更新。如果你看到一个问题，反复地问你“从L到R这个范围内的xx是什么？”或者“把L到R这个范围内的数都改成xx”，那线札树可能就是你的答案。 它的核心思想就是“分治”。把一个大区间，一分为二，变成两个小区间，直到每个区间只包含一个元素。这样，一个长度为N的数组，就对应了一棵满二叉树（或近似满二叉树），树的深度是 O(logN)。每一次查询和更新，我们都只需要沿着树的一条路径走到底，所...00
MMrHeinxiaoh.hashnode.dev·Oct 4, 2025 · 14 min read优先队列PriorityQueue很多时候，我们处理数据不只是简单地存进去、取出来，而是希望每次取出的都是当前这批数据里"最"牛的那个，比如最大、最小、最重要等等。普通队列是先进先出，栈是后进先出，都满足不了这个需求。这时候，优先队列就登场了。 你可以把它想象成一个VIP候机室，不管你什么时候来的，只要你的"优先级"最高（比如是头等舱、白金会员），你就能最先登机。在算法里，这个"优先级"通常就是元素的大小。 Java里 PriorityQueue 就是它的标准实现，底层是一棵二叉堆（小顶堆）。这意味着，它能用 O(logN) 的...00
MMrHeinxiaoh.hashnode.dev·Oct 4, 2025 · 12 min read并查集（Disjoint Set Union, DSU）并查集（Disjoint Set Union, DSU）是一种非常有用的数据结构，主要用来处理一些不相交集合的合并及查询问题。听起来很抽象，但其实核心就两个操作： find：查找一个元素属于哪个集合（通常通过返回该集合的代表元素，也就是根节点）。 union：将两个元素所在的集合合并成一个集合。 为了让find操作更快，我们通常会加上一个“路径压缩”的优化。为了让合并后的树结构更平衡，会加上“按秩合并”或“按大小合并”的优化。 10.2 一维并查集的应用算法设计 10.2.1 以图判树...00
