学习时间性价比最高的数据结构--线段树

如果时间太紧张，紧张到只能学一种数据结构，那么它一定是线段树。线段树支持区间修改，区间查询，能完全替代单调队列、树状数组，学一个相当于多学了另外两种，虽然效率要低一些，空间需求大一些，但能满足绝大多数情况的要求。

一、单调队列

单调队列能在O(n)时间内维护滑动区间最值，用线段树替代的话复杂度O(nlogn)，虽然慢但不也慢不了多少。

二、树状数组

普通树状数组可以支持区间查询和单点更新，线段树都能办到，复杂度都是O(logn)，只是线段树常数较大而已。