线段树

线段树是一种树形结构，主要用于维护区间信息，可以在O(logN)的时间复杂度内实现单点修改、区间修改、区间查询、区间求和等操作。

看一个简单的例子，给定一个数组，要求数组的区间和，比如数组[1, 3, -1, 2, 5]，求数组[1,3]区间内元素之和，一般来说可以通过下面两种方式来实现。

1. 直接遍历数组区间，然后将元素相加，例如，sum[1,3]=3+(-1)+2=4，时间复杂度是O(N)。
2. 先求出数组的前缀和，然后再通过前缀和求区间和，例如，prefix=[1, 4, 3, 5, 10]，sum[1,3]=prefix[3]-prefix[0]=4，求区间和的这个操作时间复杂度是O(1)。

目前来看第二种方式更高效一点，但是如果数组是可变的呢？对于第一种方式，修改数组元素只需要O(1)的时间复杂度，而对于第二种方式，修改完数组元素后需要更新前缀和数组，这个更新的操作时间复杂度是O(N)。而线段树就是能够让修改元素和区间求和这个两个操作的时间复杂度都在O(logN)级别，这样就弥补了上述两种办法的缺点，下面看看线段树的逻辑结构。

下面看看线段树的实现，这里我们使用数组来保存线段树节点。

上面的实现是用来计算区间求和的代码，稍微修改一下还可以实现更多功能，比如区间求最值。