线段树基础教程
⚠️ 内容不完整：原网页使用 JavaScript 动态加载，仅获取到 41 行简介，缺少正文详细内容（三种线段树的实现原理、代码示例等）
核心要点
线段树定义
线段树是 二叉树结构 的衍生，用于高效解决数组的 区间查询 和 区间动态修改 问题。
时间复杂度：
- 区间查询：O(log N)，支持任意长度区间
- 区间动态修改：O(log N)，支持任意长度区间
- N 为数组中的元素个数
三种线段树变体
1. 基本线段树
- 包含方法：
query（区间查询）、update（单点修改） - 特点：叶子节点是数组中的元素，非叶子节点是索引区间（线段）的汇总信息
- 限制：必须输入
nums数组进行构建
2. 动态线段树（动态开点）
- 运用「动态开点」技巧优化内存开销
- 适用场景：处理稀疏数据，避免在大区间（如 [0, 10^9]）上浪费空间
- 优化：不需要一开始就分配 10^9 的空间，而是按需动态创建节点
3. 懒更新线段树
- 新增方法：
rangeAdd/rangeUpdate（区间更新） - 运用「懒更新」技巧
- 核心思想：不需要立即更新区间内所有叶子节点，而是将更新值缓存在非叶子节点中
- 传播时机：当调用
query方法进行区间查询时，才逐渐将更新值向叶子节点传播 - 时间复杂度：O(log N) 完成任意长度区间更新
前置知识
- 二叉树：理解树结构和遍历方法
- 二叉树的递归/层序遍历
相关概念
- 线段树（Segment Tree）
- 动态开点
- 懒更新（Lazy Update）
- 区间查询（Range Query）
- 区间修改（Range Update）