线段树 - 一维区间查询的利器

线段树是一种数据结构，用于解决一维区间查询问题。它可以在 'O(log n)' 的时间内进行区间查询和单点修改。线段树是一种二叉树，其中每个叶子节点表示一个单独的元素，每个非叶子节点表示一组元素的区间。每个节点都有一个区间，其中左右子树分别表示该区间的左半部分和右半部分。

线段树的构建过程可以通过递归实现。对于一组元素 'A'，可以将其分为两个子区间 'A_1' 和 'A_2'，然后递归地构建线段树。每个节点的值可以通过对其子节点的值进行操作得到，例如求和、最大值、最小值等。

线段树可以支持以下操作：

1. 区间查询：查询区间 '[a,b]' 中的元素，可以通过递归地查询左右子树来实现。

2. 单点修改：修改某个元素的值，可以通过递归地修改左右子树来实现，同时更新其父节点的值。

线段树的优点是可以在 'O(log n)' 的时间内进行区间查询和单点修改，适用于对静态数据进行频繁查询和修改的场景。缺点是需要额外的空间来存储线段树，且构建线段树的时间复杂度为 'O(n)'。