让我们通过考虑下面的问题来理解线段树。
给定一个数组arr[0 . . . n-1]，我们要对数组执行这样的操作：
1 计算从下标l到r的元素之和，其中 0 <= l <= r <= n-1
2 修改数组指定元素的值arr[i] = x，其中 0 <= i <= n-1
一个简单的方案是从l到r执行循环，计算给定区间的元素之和。更新值的时候，简单地令arr[i] = x。第一个操作花费O(n)的时间，第二个操作花费O(1)的时间。
第二个方案是创建另外一个数组来存储从下标i开始的元素之和。这样一来，给定区间之和可以用O(1)的时间计算，但是更新需要花费O(n)的时间。这种方法适用于需要大量查询而更新操作较少的场景。
如果查询和更新的次数一样多呢？我们可以在O(log n)的时间内完成上述两种操作吗？
我们可以使用线段树来实现在O(log n)时间内完成上述两种操作。
线段树的表示：
1. ...