线段树的原理、懒标记与应用
哪些公司问过
答案要点
- 每个节点存一段区间的聚合值,根为全区间,叶为单点,数组实现通常开 4n
- 单点修改和区间查询都是 O(log n),建树 O(n)
- 懒标记:整区间被覆盖时只更新本节点并打标记,访问子节点时再下传
- 典型应用:区间和/最值、区间加乘、扫描线、权值线段树求第 k 小
- 对比树状数组:BIT 更短更快但偏前缀和类运算,线段树更通用但常数大
易错点
- 查询或修改前忘记 pushdown,导致子节点值过期
- 数组只开 2n,n 不是 2 的幂时下标越界
- 区间加的懒标记更新和要乘区间长度,漏乘会算错
面试官常见追问
- 同时有区间加和区间乘,懒标记怎么处理?
- 值域很大怎么办?
- 为什么数组要开 4n?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场