线段树基本结构

一句话理解

线段树把区间递归分成左右两半。

为什么要学

每个节点管一段。

讲解

满二叉树，约 4n 空间。支持区间查询修改。

例子

根管 [1,n]，左 [1,mid]，右 [mid+1,n]。

常见错误

• 只开 2n 某些实现会炸，初学开 4n。
• 动态开点另说。