区间维护问题

动态维护 (对区间维护问题的两个操作求和和修改的时间复杂度做一个均衡, 使得总复杂度降低, 同时支持两种操作)

修改和维护时间复杂度都是$O(logn)$, 但是线段树常数大一些$O(4logn)$, 树状数组$O(logn)$

• 线段树: 维护的是任意区间和, 以及区间最值。
• 树状数组: 能维护前缀区间的最值和前缀和, 可求任意区间和, 但是不能维护任意区间最值。
  因为1~10的最大值和1~5的最大值取一个max, 它不一定是5~10的最大值。
  线段树与树状数组的区别

静态维护 (只维护, 不能够在中途添加元素, 开始就给定区间元素, 要实现也是可以暴力做动态维护的, 但是由于修改的时间复杂度过高会导致时间复杂度很高, 不考虑, 要动态维护就用数据结构)

• RMQ: 维护任意区间最值
• 前缀和算法: 维护前缀区间和, 前缀区间最值, 可求任意区间和.

区间操作问题

• 贪心