从‘校门外的树’到线段树：用一道OJ题带你入门区间查询与修改
当你第一次看到"校门外的树"这道题时，可能会觉得这不过是个简单的数组标记问题。确实，对于L=10000这样的小规模数据，暴力解法完全可行。但想象一下，如果L扩大到10^9呢？这时传统的数组解法就会因为内存不足而崩溃。这正是算法设计中常见的"规模扩展"问题，也是我们今天要探讨的核心。
1. 问题分析与基础解法
让我们先理解题目本质：在一条长度为L的马路上，初始每个整数点都有一棵树。给定M个区间，需要移除这些区间内的所有树，最后统计剩余树木数量。用编程术语来说，这就是一个典型的区间覆盖统计问题。
对于小规模数据（如L≤10000），最直观的解法是使用标记数组：
int trees[10001] = {0}; // 初始化所有位置为0表示有树 for(int i =0; i<m; i++){ scanf("%d%d", &a, &b); for(int j=a; j<=b; j++){ trees[j] = 1; // 标记为1表示树被移除 } } int remaining = 0; for(int i=0; i<=l; i++){ if(trees[i] == 0) remaining++; }这种解法时间复杂度为O(M×L)，当L=10000、M=100时，运算量在百万级别，现代计算机完全可以轻松处理。但问题在于：
- 当L=10^9时，需要约4GB内存（假设int为4字节），显然不现实
- 即使内存足够，O(M×L)的时间复杂度在M=10^5时将达到10^14次操作，远超合理范围
2. 离散化：处理大规模区间的第一把钥匙
面对大规模数据，我们需要更聪明的办法。离散化(Discretization)技术应运而生，它能将无限或极大的数据范围映射到有限的点上。
离散化的核心思想是：只关注区间的端点，忽略中间连续的部分。具体到本题：
- 收集所有区间的起点和终点
- 对这些点进行排序和去重
- 相邻两点之间的区域要么全部被移除，要么全部保留
实现步骤示例：
// 假设所有区间端点已存储在数组points中 sort(points.begin(), points.end()); points.erase(unique(points.begin(), points.end()), points.end()); int result = 0; for(int i=1; i<points.size(); i++){ if(!is_removed(points[i-1], points[i])){ // 判断该区间是否被任何原始区间覆盖 result += points[i] - points[i-1] -1; // 计算区间内树的数量 } }离散化将复杂度从O(L)降到了O(M log M)，因为主要开销在于排序。这使得处理L=10^9、M=10^5的数据成为可能。
提示：离散化后判断区间是否被覆盖时，可以使用前缀和或差分数组优化查询效率
3. 线段树：区间操作的终极武器
虽然离散化解决了内存问题，但对于需要频繁区间查询和修改的场景（如动态增减区间），离散化就显得力不从心了。这时，线段树(Segment Tree)闪亮登场。
线段树是一种二叉树结构，每个节点代表一个区间，能够高效处理区间查询和更新操作。对于本题，线段树可以实现：
- 区间更新：标记某个区间的树被移除
- 区间查询：统计未被移除的树的数量
基础线段树节点结构：
struct SegmentTreeNode { int left, right; // 节点代表的区间范围 int count; // 该区间内剩余的树的数量 bool lazy; // 懒惰标记，表示该区间是否被整体移除 SegmentTreeNode *leftChild, *rightChild; void pushDown() { if(lazy && left != right) { leftChild->count = 0; rightChild->count = 0; leftChild->lazy = true; rightChild->lazy = true; lazy = false; } } };关键操作实现：
// 区间更新 void update(SegmentTreeNode* node, int l, int r) { if(node->right < l || node->left > r) return; if(l <= node->left && node->right <= r) { node->count = 0; node->lazy = true; return; } node->pushDown(); update(node->leftChild, l, r); update(node->rightChild, l, r); node->count = node->leftChild->count + node->rightChild->count; } // 构建线段树 SegmentTreeNode* build(int l, int r) { SegmentTreeNode* node = new SegmentTreeNode{l, r, r-l+1, false, nullptr, nullptr}; if(l != r) { int mid = (l + r) / 2; node->leftChild = build(l, mid); node->rightChild = build(mid+1, r); } return node; }使用线段树解决问题：
SegmentTreeNode* root = build(0, L); for(auto &range : ranges) { update(root, range.start, range.end); } int remaining = root->count;线段树的优势在于：
- 构建时间复杂度：O(L)
- 每次更新/查询时间复杂度：O(log L)
- 特别适合动态区间操作场景
4. 方案对比与选择指南
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 | 限制条件 |
|---|---|---|---|---|
| 暴力数组法 | O(M×L) | O(L) | L较小(≤10^6) | 内存限制 |
| 离散化 | O(M log M) | O(M) | 静态区间，只需最终结果 | 动态操作困难 |
| 线段树 | O(M log L) | O(L) | 需要动态更新和查询 | 实现较复杂 |
选择建议：
- 对于一次性静态查询且L极大时，优先考虑离散化
- 需要支持动态操作时，必须使用线段树
- 数据规模很小时，简单数组法最直观易实现
5. 线段树的扩展应用
线段树的价值远不止于此，它还能解决更多复杂问题：
- 区间最值查询：每个节点存储区间最大值/最小值
- 区间和查询：支持区间增减和求和操作
- 二维线段树：处理平面区域问题
- 持久化线段树：记录历史版本，解决可持久化问题
以区间和为例，节点结构稍作修改：
struct SegmentTreeNode { int left, right; int sum; // 区间和 int add; // 懒惰标记，表示区间每个元素要增加的值 void pushDown() { if(add != 0) { leftChild->sum += add * (leftChild->right - leftChild->left +1); rightChild->sum += add * (rightChild->right - rightChild->left +1); leftChild->add += add; rightChild->add += add; add = 0; } } };这种灵活性使得线段树成为算法竞赛和工程开发中的重要工具。
