1、清 华 大学 张 昆 玮*清 华 大学 张 昆 玮 2*根据 D. E. Knuth 的分 类 方法计 算机算法可以分 为 两 类 ：*数 值 算法与非数 值 算法*其中的非数 值 算法包括：*索引*分 类*统计*清 华 大学 张 昆 玮 3*大家都 说 ：*常数很大？*不好 写？*难 调试 ？*想不到？*清 华 大学 张 昆 玮 4*POJ上的某 题 ， 时 限很 紧 *大家都用 树 状数 组 ， 但是有人只会用 线 段 树 呢？*而且我可以 轻 易改出一道不能用 树 状数 组 的 题*在 线 段 树 一次次 TLE后，有一个 ID发 帖抱怨*“下次写一个 汇编 版 非 递归 线 段 树 ，
2、再超 时 ？ ”*可是大家都知道，超 时 的代 码 已 经 2k了。*其 实 我写的 就是 线 段 树 。很快，而且不到 1k。*清 华 大学 张 昆 玮 5*运行速度快*适 应 能力 强*编 写方便*结 构 简单*容易 调试*关 键 在于 灵活 实现为 什么在 算法 导论 和黑 书 中都 难见 到其踪迹？*清 华 大学 张 昆 玮 6*清 华 大学 张 昆 玮 7*计 算几何在 长 期的 发 展中，诞 生了 许 多 实 用的数据 结 构。*区 间查询 ，穿刺 查询 都是 计 算几何解决的 问题*作 为 特例中的特例， 线 段 树 解决的 问题 是：*一 维 空 间 上的几何 统计*高 维 推
3、广（ kd-tree & ）可以 进 行正交 查询*由于 竞赛 中涉及 计 算几何的内容有限，不展开*清 华 大学 张 昆 玮 8*线 段 树 把数 轴 分成区 间 来 处 理*如 8,10), 10,11), *实际 上我 们 面 对 的往往是离散量*竞赛 中 出 现 的 线 段 树 往往因此退化 为 “点 树 ”*即，最底 层 的 线 段只包含一个点：*如： 8,9)中只有整点 8而已*在 之后的 讨论 中，我 们 不再区 别 “点 树 ”与 线 段树如果我 给 MM的第一印象不到 80分的 话 是不是老老 实实 地早点 罢 手比 较 好？*清 华 大学 张 昆 玮 9*清 华 大学 张 昆 玮 10
