当我们在一段连续的区间上进行操作，又有时间复杂度的要求时，就可以看看线段树。

登录以参加训练计划

通过在有序的数据上分治，我们可以得到logn级别的提升。

利用空间换时间的预计算策略，我们能够得到O(1)级别的提升

把这两种加起来，就有了线段树。

要符合线段树，必须要保证以下几个属性

1. 有序
2. 管理的权值有有传递性：仅通过子树的权值就可以算出父节点的权值
3. 操作的目标是连续的区间

实现这棵树，可以用指针法，也可以用二叉树的数组表示法。