定义

• 什么是线段树

  线段树是一种二叉搜索树，每个节点都存储了一个区间的问题。

• 能够解决的问题

  序列维护修改以及查询区间上的最值、求和等，修改和查询的时间复杂度为 \(O\)(\(log\) \(n\))。

• 与其他 RMQ 算法的区别

  算法	适用范围	优点	缺点
  线段树	动态	可执行的操作多	常数大
  树状数组	动态	好写	扩展性较弱
  ST 表	静态	\(O\)(\(1\)) 查询	不支持在线操作

  tips：

  • 动态：在查询过程中，数字可能会发生一定程度的修改。

  • 静态：数字不会发生改变