线段树详解：动态范围更新与区间查询

"快速操作-细讲线段树" 线段树是一种数据结构，用于高效地处理区间上的数值操作，如动态更新和区间查询。它适用于处理一系列元素，并且需要支持对连续子序列进行加法操作（Add）以及计算子序列的和（Query）。线段树通常用于解决动态范围内的最值问题，比如区间最小值或最大值。 线段树的构造基于分治策略。每个节点代表一个区间，例如，节点T(a,b)维护的是数组中的区间[a,b)的信息。如果区间长度b-a大于1，那么该节点会有两个子节点，分别对应区间的左右两部分。当b-a等于1时，节点成为叶节点，直接存储数组中的一个元素值。线段树的结构是一个自底向上的递归定义，类似一棵满二叉树。 线段树具有以下性质： 1. 结点数：线段树的总结点数不超过2n，当处理的数列长度为n时。 2. 深度：由于线段树近似满二叉树，其深度不超过log(2n)。 3. 线段分解：线段树将任意长度为L的线段分解成不超过2logL条更短的线段，从而能在O(logn)时间内完成大部分查询操作。 线段树的存储方式主要有三种： 1. 链表存储：每个节点包含指向子节点的指针，灵活但空间效率较低。 2. 数组模拟链表：利用数组的索引关系来模拟链表，节省空间，但访问路径依赖于数组索引。 3. 堆结构存储：通过堆来实现线段树，适用于某些特定场景。 对于数组存储的线段树，假设区间范围是2^n，可以按照满二叉树的方式构建，例如，可以声明一个大小为2n-1的数组minv来存储每个节点的最小值。初始化时，将所有节点设置为无穷大。在进行修改操作（Update）时，先将新的值赋予对应的叶节点，然后自底向上更新父节点的值。查询操作（Query）则采用分治策略，递归地在子节点中寻找区间内的最小值。 例如，给出以下代码片段： ```cpp // 初始化线段树 void init(int n) { N = 1; while (N < n) N *= 2; for (int i = 0; i < 2 * N - 1; i++) minv[i] = INT_MAX; } // 修改操作 void update(int k, int a) { k += N - 1; minv[k] = a; while (k > 0) { k = (k - 1) / 2; minv[k] = min(minv[k * 2 + 1], minv[k * 2 + 2]); } } // 查询操作 int query(int o, int l, int r, int a, int b) { if (r <= a || b <= l) return INT_MAX; if (a <= l && r <= b) return minv[o]; else { int v1 = query(o * 2 + 1, l, (l + r) / 2, a, b); int v2 = query(o * 2 + 2, (l + r) / 2, r, a, b); return min(v1, v2); } } ``` 这些函数展示了如何在数组存储的线段树上执行Update和Query操作。注意，这里的代码是针对求解区间最小值问题，而对于“快速操作-细讲线段树”中提到的Add和Query操作，线段树同样适用，只需要稍微调整即可，比如在Update操作中将加法应用到节点值上，而Query操作则返回区间和。