面试题库 › 客户端 › 线段树的原理、懒标记与应用

线段树的原理、懒标记与应用

难度 ★★☆在 1 场真实面经中被问到 方向:客户端考点:树与二叉树

哪些公司问过

快手1

常见岗位:游戏客户端

答案要点

  1. 每个节点存一段区间的聚合值,根为全区间,叶为单点,数组实现通常开 4n
  2. 单点修改和区间查询都是 O(log n),建树 O(n)
  3. 懒标记:整区间被覆盖时只更新本节点并打标记,访问子节点时再下传
  4. 典型应用:区间和/最值、区间加乘、扫描线、权值线段树求第 k 小
  5. 对比树状数组:BIT 更短更快但偏前缀和类运算,线段树更通用但常数大

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题