Skip to content

2026

线段树

为什么需要线段树?

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

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

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

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

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

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

Unity 中的 Attribute-based 反射机制

  • "反射" 的本质在于:在 运行时 读取程序的元信息(metadata),从而动态地访问/读取/调用对象的属性和方法

  • 此外,Unity 支持通过 tag(实际上是 Attribute)实现一些妙妙小功能:`

    • [Range(0,1)]可将变量的取值范围限制到 $[0,1]$
    • [Header("sth")] 会在 Inspector 菜单中显示小标题 "sth"

我们将在本文中讨论其实现原理与自定义实现