线段树代码

### 线段树代码详解 #### 一、线段树简介 线段树是一种用于区间查询和更新操作的数据结构，常用于解决一类区间问题。它通过对数组进行分治处理来实现快速查询与修改，时间复杂度为O(log n)。 #### 二、代码解析 在给出的代码片段中，实现了一个基础的线段树结构，主要用于存储区间最小值、最大值和最小差值，并支持元素添加、删除以及查询最小差值的操作。 #### 三、关键数据结构 **Node 结构体定义** ```cpp struct Node { int min; // 区间最小值 int max; // 区间最大值 int min_diff; // 区间最小差值 } ``` - **min**: 表示该节点所覆盖区间的最小值。 - **max**: 表示该节点所覆盖区间的最大值。 - **min_diff**: 表示该节点所覆盖区间内的最小差值，即区间内的最小值与最大值之差的最小值。 #### 四、初始化函数 ```cpp void init() { for (int i = 1; i < (N << 1); i++) { node[i].min = INF; node[i].max = -INF; node[i].min_diff = INF; } } ``` 初始化线段树的所有节点，将所有节点的最小值设为正无穷，最大值设为负无穷，最小差值设为正无穷，确保任何新加入的元素都能被正确处理。 #### 五、辅助函数 - `min`: 返回两个整数中的较小值。 - `max`: 返回两个整数中的较大值。 - `query`: 返回线段树根节点的最小差值，如果不存在有效区间则返回 -1。 - `get_left_child`: 返回指定节点的左子节点。 - `get_right_child`: 返回指定节点的右子节点。 - `get_parent`: 返回指定节点的父节点。 - `get_node`: 将一个索引转换为线段树中的节点索引。 #### 六、核心函数 - **update**：更新节点的最小值、最大值和最小差值。 ```cpp void update(int p) { int left_child = get_left_child(p); int right_child = get_right_child(p); node[p].min = min(node[left_child].min, node[right_child].min); node[p].max = max(node[left_child].max, node[right_child].max); node[p].min_diff = min(node[left_child].min_diff, node[right_child].min_diff); node[p].min_diff = min(node[p].min_diff, node[right_child].min - node[left_child].max); } ``` - **add**：向线段树中添加元素。 ```cpp void add(int m) { int cur = get_node(m); if (node[cur].min == INF) { node[cur].min = m; node[cur].max = m; do { cur = get_parent(cur); update(cur); } while (cur > 1); } } ``` - **remove**：从线段树中移除元素。 ```cpp void remove(int m) { int cur = get_node(m); if (node[cur].min < INF) { node[cur].min = INF; node[cur].max = -INF; do { cur = get_parent(cur); update(cur); } while (cur > 1); } } ``` #### 七、主函数逻辑 主函数中首先初始化了线段树，然后读取测试用例数量，对于每个测试用例，读取一系列操作命令，包括添加元素、删除元素和查询最小差值。最后根据指令执行相应的操作。 #### 八、应用场景 线段树适用于需要频繁进行区间查询或更新的场景，如统计区间内特定数值的数量、计算区间和等。 通过以上分析可以看出，这段代码实现了基于线段树的基本功能，能够有效地处理区间内的元素添加、删除及查询操作，是理解和应用线段树的一个良好示例。