线段树

原文oi wiki:SegTree

简述

线段树（Segment Tree）是一种二叉树结构，主要用于高效地维护区间信息，例如区间和、区间最值、区间最大公约数等等。

你可以把它当作一个比树状数组（Binary Indexed Tree）更万能的数据结构，因为它不仅支持单点修改和区间查询，还可以通过扩展支持区间修改、区间最值查询等操作。