线段树专辑

在自然数，且所有的数不大于30000的范围内讨论一个问题：现在已知n条线段，把端点依次输入告诉你，然后有m个询问，每个询问输入一个点，要求这个点在多少条线段上出现过； 最基本的解法当然就是读一个点，就把所有线段比一下，看看在不在线段中； 每次询问都要把n条线段查一次，那么m次询问，就要运算m*n次，复杂度就是O(m*n) 这道题m和n都是30000，那么计算量达到了10^9；而计算机1秒的计算量大约是10^8的数量级，所以这种方法无论怎么优化都是超时 因为n条线段是固定的，所以某种程度上说每次都把n条线段查一遍有大量的重复和浪费； 线段树就是可以解决这类问题的数据结构 举例说明：已知线段[2,5] [4,6] [0,7]；求点2,4,7分别出现了多少次 在[0,7]区间上建立一棵满二叉树：（为了和已知线段区别，用【】表示线段树中的线段） 【0,7】 / \ 【0,3】 【4,7】 / \ / \ 【0,1】 【2,3】 【4,5】 【6,7】 / \ / \ / \ / \ 【0,0】 【1,1】 【2,2】 【3,3】 【4,4】 【5,5】 【6,6】 【7,7】 每个节点用结构体： struct line { int left,right; // 左端点、右端点 int n; // 记录这条线段出现了多少次，默认为0 }a[16]; 和堆类似，满二叉树的性质决定a[i]的左儿子是a[2*i]、右儿子是a[2*i+1]; 然后对于已知的线段依次进行插入操作： 从树根开始调用递归函数insert 线段树是一种高效的数据结构，用于处理动态维护区间上的数据查询和更新问题。它通过将一个区间分解成多个子区间并存储在二叉树的节点中，使得可以在对数时间内完成区间查询和更新操作，避免了传统的暴力遍历方法带来的线性时间复杂度。 线段树的基本构建过程如下： 1. **初始化**：根据给定的区间范围，建立一棵满二叉树，每个节点代表一个子区间。例如，对于区间[0, 7]，会生成如下的满二叉树： ``` 【0,7】 / \ / \ 【0,3】 【4,7】 / \ / \ 【0,1】 【2,3】 【4,5】 【6,7】 ``` 2. **节点结构**：每个节点通常包含左右端点和一个附加数据字段，例如用于记录线段出现次数的`n`。在这个例子中，结构体`line`定义了线段树节点的属性。 ```cpp struct line { int left, right; int n; // 记录这条线段出现了多少次，默认为0 } a[16]; ``` 3. **插入操作**：将给定的线段依次插入线段树中，通过递归地从根节点开始调用`insert`函数，将线段划分到相应的子区间内。 4. **区间查询**：对于每个询问，如查询某个点在多少条线段上出现过，可以自顶向下遍历线段树，对经过的节点累加它们的`n`值，最后得到答案。 5. **区间更新**：若要修改某点的值或者增加/减少某区间的值，同样从根节点开始，根据更新范围找到对应的子树，然后执行相应的操作，之后可能需要调用`PushUp`函数来更新父节点的信息。 6. **优化技巧**：在实现线段树时，可以使用一些优化策略，比如在节点中保存更多信息以减少不必要的计算，或者使用`PushDown`函数将信息下推到子节点，提高效率。 在实际编程中，线段树的应用不仅限于计算点在多少条线段上出现，还可以用于区间求和、区间最值等操作。例如，题目"敌兵布阵"和"I Hate It"展示了如何使用线段树实现单点更新和区间查询。在"敌兵布阵"中，线段树用于维护区间求和，而"I Hate It"则演示了如何使用线段树找到区间内的最值。 线段树的灵活性和高效性使其成为解决大量区间查询和更新问题的首选工具。随着对更高级数据结构如Splay树的学习，线段树的实现方式可以变得更优雅、简洁，进一步提升性能。在编写线段树的代码时，注意合理设置节点数量，以及使用预定义变量简化表示，可以使得代码更加清晰易懂。