为什么要使用线段树
最经典的线段树：区间染色
有一面墙，长度为n，每次选择一段墙染色。
m次操作后，我们可以看见多少种颜色？
m次操作后，我们可以在[i,j]区间内看见多少种颜色？
|
使用数组实现 |
使用线段树 |
| 染色操作（更新区间） |
O(n) |
O(logn) |
| 查询操作（查询区间） |
O(n) |
O(logn) |
另一类问题：区间查询
查询一个区间[i,j]的最大值，最小值，或者区间数字和
实质：基于区间的统计查询
2017年注册用户中消费最高的用户？消费最少的用户？（动态更新）
区间是固定的，只是区间中的元素不一样，所以可以直接用静态数组。
