线段树模板：单点修改与区间查询

"区间/单点修改，区间求和问题的线段树模板及实现" 线段树是一种数据结构，用于高效地处理区间查询和修改问题。它在算法设计中有着广泛的应用，尤其是在处理动态范围查询和更新的问题时。线段树通过分治的思想将问题分解，将大问题转化为小问题的解决，从而达到高效运算的目的。 在这个模板中，线段树的节点定义为`struct Tree`，包含了三个属性：`l`表示当前节点代表的线段左边界，`r`表示右边界，`sum`存储了该线段的累加和。线段树的构建和查询操作主要通过递归实现。 1. **线段树构建（build）**： 构建线段树的过程是从根节点开始，逐层向下填充每个节点。如果一个节点代表的是一个单一元素（叶子节点），则其`sum`值等于该元素的初始值。否则，将该区间分为两半，分别对左子树和右子树进行构建，并将子树的`sum`值累加到当前节点。 2. **区间查询（search）**： 区间查询的目的是找出给定区间内的累加和。首先判断当前节点是否完全包含在查询区间内，若包含则直接返回其`sum`；若不包含，根据子节点与查询区间的交集情况，递归查询左子树和右子树。 3. **单点修改（add）**： 单点修改是指在某一个位置增加或减少一个数值。从根节点开始，沿着路径找到要修改的叶子节点，然后进行累加操作。如果在分支过程中，待修改的位置位于当前节点的左子树，就向左子树递归；否则，向右子树递归，直到找到对应的叶子节点。 线段树的优势在于其查询和修改的时间复杂度为O(logN)，其中N是区间元素的总数。这使得线段树在处理大规模数据时表现出良好的效率。此外，线段树还可以支持更复杂的操作，如区间最大值、区间最小值、区间平均值等，只需稍作修改即可适应不同的需求。 在实际应用中，线段树常用于处理动态数组的查询和更新，例如在线统计一段区间内的和、求解最值问题等。在竞赛编程、数据结构与算法课程中，线段树是必备的知识点之一，对于提升解决问题的能力非常有帮助。