线段树（一） 线段树是一种维护区间信息常用的树形数据结构。在全国青少年信息学奥林匹克竞赛大纲内难度评级为 6，是提高级中开始学习的数据结构。 本篇文章讨论的内容是线段树的基本结构与操作、线段树的延迟更新。 代码模板 代码模板-线段树 基本结构 ...

线段树用完全二叉树的数组存储，节点 p 的左右儿子为 p<<1 和 p<<1|1，开 4 倍空间。每个节点维护一个区间的信息，建树/修改/查询都在 O(log⁡n)O(\log n)O(logn) 的一条树链上完成。 单点...