第4章笔记：基础数据结构的算法化使用

目标

按操作契约选择栈、队列、堆、并查集和树状数组。

七课依赖

• 单调栈与最近更大元素：围绕单调栈与最近更大元素先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 单调队列与区间最值：围绕单调队列与区间最值先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 堆与动态Top-K：围绕堆与动态Top-K先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 并查集与连通分量：围绕并查集与连通分量先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 树状数组的低位分解：围绕树状数组的低位分解先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 线段树的区间合并：围绕线段树的区间合并先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 可持久化思想入口：围绕可持久化思想入口先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。 本课必须再检查边界输入、整数溢出、下标和不可行状态。

复杂度与适用条件表

算法对象	不变量/复杂度来源	使用边界
单调栈与最近更大元素	围绕单调栈与最近更大元素先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
单调队列与区间最值	围绕单调队列与区间最值先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
堆与动态Top-K	围绕堆与动态Top-K先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
并查集与连通分量	围绕并查集与连通分量先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
树状数组的低位分解	围绕树状数组的低位分解先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
线段树的区间合并	围绕线段树的区间合并先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
可持久化思想入口	围绕可持久化思想入口先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	数据结构复杂度依赖实现；路径压缩与按秩合并给的是摊还界。 本课必须再检查边界输入、整数溢出、下标和不可行状态。

复盘

每题保存暴力、优化、证明、四组边界测试和首个WA输入；一周后换数据重做。