余弦の博客

文章介绍了线段树在解决RMQ（区间最值查询）及区间修改问题中的应用，重点讲解了线段树的数组存储方式、节点编号规则（左子节点为2n，右子节点为2n+1），并详细说明了点修改和区间修改（如区间加、区间加乘）的实现方法，强调了懒标记的使用和pushdown操作中“先乘后加”的关键逻辑。

文章介绍了二叉搜索树（BST）的基本概念、核心操作（查找、插入、删除）以及平衡二叉树（AVL树）的结构与调整机制。通过分析插入序列生成的BST，进一步说明了如何判断不同序列是否能生成同一棵二叉搜索树，方法是构建一棵树并按顺序验证各序列在该树中的查找路径是否一致。

ST表是一种用于解决区间最值查询的高效算法，通过O(nlogn)预处理实现O(1)查询，适用于静态数组的范围最大值或最小值查询，但不支持在线修改。

文章系统介绍了树和二叉树的基本概念、术语、性质及存储结构。重点讲解了树的定义、结点属性、层次与深度、森林概念，以及二叉树的五种形态、遍历方法（先序、中序、后序、层序）和存储方式（顺序与链式），并总结了二叉树的重要性质和查找操作的基本方法。

本文介绍了队列的抽象数据类型及其两种存储实现方式：顺序存储（循环队列）和链式存储。顺序存储通过循环队列优化了空间利用率，避免了“假溢出”问题；链式存储则通过单链表实现，操作在链表两端进行，适用于动态变化的队列场景。

本文介绍了堆栈的抽象数据类型及其顺序和链式存储实现，重点讲解了栈的入栈、出栈操作，并以中缀表达式转为后缀表达式为例说明了栈的应用。此外，还列举了栈在函数调用、递归、深度优先搜索和回溯算法中的实际应用。

文章介绍了广义表作为线性表的推广，允许元素为单元素或另一个广义表，并阐述了多重链表的概念及其在存储复杂数据结构中的应用。以稀疏矩阵为例，通过十字链表实现高效存储，仅保存非零元素，并利用行指针、列指针和标记域实现矩阵的有序链接与管理。

文章介绍了线性表的抽象数据类型及其顺序存储和链式存储两种实现方式。顺序表通过数组存储元素，支持高效随机访问和基本操作如插入、删除、查找等；链式存储则通过链表节点连接元素，插入和删除操作无需移动元素，仅修改指针，具有更好的动态性。文章通过代码演示说明了两种存储结构的操作流程和运行结果。