Skip to content

数据结构

线段树

为什么需要线段树?

  • 如果我们想知道数组 arr 的任意区间和 sum(arr[i:j]),那么维护 前后缀和 是一个不错的选择

    => 只需预处理一次、之后所有查询仅需 \(O(1)\)

    • 但如果数组中的值需要 被修改呢 ?此时需要重新计算 所有 前后缀和

    • 此外,前后缀和也不能提供对区间 最大/最小值 的快速查询支持

  • 线段树(Segment Tree)就是为维护这类 需要动态修改的区间信息 设计的,可以在 \(O(\log{N})\) 内实现单点修改、单点查询、区间修改,以及区间查询

本文仅介绍最基本的线段树实现(递归建树 + 懒更新)