node

笛卡尔树通过结合二叉搜索树和堆性质，将RMQ问题转化为LCA问题，利用单调栈在O(n)时间内构建，并配合DFS与稀疏表实现O(1)查询，适用于静态数据的高效区间最值查询。 笛卡尔树（Cartesian Tree）是一种结合了二叉搜索树和堆性质的数据结构，常用于解决RMQ（Range Minimum/…

C++中可通过智能指针模拟自动内存管理，std::shared_ptr基于引用计数实现对象生命周期管理，避免内存泄漏；循环引用问题可用std::weak_ptr解决；自定义SimplePtr可演示原理，但实际推荐使用标准库智能指针。 在C++中，虽然没有像Java或C#那样的自动垃圾回收机制（GC）…

内存池通过预分配大块内存并内部管理分配与释放，减少系统调用开销。它适用于频繁创建销毁固定大小对象的场景，提升分配速度与缓存局部性，降低碎片风险。实现上采用空闲链表管理可用槽位，结合placement new进行对象构造。虽然存在不适用变长对象、需手动调用析构等限制，但在游戏、实时系统中仍能显著优化性…

深度优先搜索（DFS）通过递归或栈实现，先访问节点并标记，再深入未访问的邻接点，回溯时继续探索其他路径，适用于图和树的遍历。 深度优先搜索（DFS）是一种用于遍历或搜索图和树的算法。它的核心思想是沿着一条路径尽可能深入地访问节点，直到无法继续为止，然后回溯到上一个节点尝试其他路径。在C++中，可以通…

AC自动机通过构建Trie树并引入失败指针实现多模式匹配，利用BFS构造fail指针以避免回溯，从而在O(n + m + k)时间内完成文本扫描，适用于敏感词过滤等场景。 AC自动机（Aho-Corasick算法）是一种高效的多模式字符串匹配算法，适合在一段文本中同时查找多个关键词。它基于Trie树…

AVL树通过四种旋转维持平衡，插入删除时更新高度并检查平衡因子，左左型右旋、右右型左旋、左右型先左旋左子树再右旋、右左型先右旋右子树再左旋，确保树高O(log n)。 AVL树是一种自平衡的二叉搜索树，通过在插入和删除节点后进行旋转操作来保持树的高度平衡。C++中实现AVL树的关键在于理解四种旋转方…

二叉搜索树通过类和指针实现，包含插入、删除、查找和中序遍历操作，其中插入和查找基于值的比较递归进行，删除需处理三种情况，中序遍历验证有序性，整体平均时间复杂度为O(log n)，但性能依赖树的平衡性。 二叉搜索树（Binary Search Tree，简称 BST）是一种重要的数据结构，它能高效地实…

首先定义节点结构，包含数据和指针；通过头插或指定位置插入实现链表创建与扩展；删除节点需调整指针并释放内存；遍历从头开始依次输出数据直至为空。 在C++中实现单链表，核心是定义节点结构和操作函数。单链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。下面介绍如何创建链表、插入节点和删除节点。…

Trie树通过共享前缀存储字符串，支持高效插入、查找和前缀匹配，时间复杂度为O(L)，适用于自动补全、拼写检查等场景。 在处理字符串前缀相关问题时，Trie树（字典树）是一种非常高效的数据结构。它通过共享前缀的方式存储字符串集合，能快速完成插入、查找和前缀匹配操作，时间复杂度为 O(L)，其中 L …

LRU缓存通过哈希表和双向链表结合实现，get和put操作均达到O(1)时间复杂度；当缓存满时淘汰最久未使用数据，利用哨兵节点简化链表操作，确保高效访问与顺序维护。 LRU（Least Recently Used）缓存淘汰算法的核心思想是：当缓存满时，优先淘汰最久未使用的数据。为了高效实现“快速访问…