从‘校门外的树’到线段树：用一道OJ题带你入门区间查询与修改

从‘校门外的树’到线段树用一道OJ题带你入门区间查询与修改当你第一次看到校门外的树这道题时可能会觉得这不过是个简单的数组标记问题。确实对于L10000这样的小规模数据暴力解法完全可行。但想象一下如果L扩大到10^9呢这时传统的数组解法就会因为内存不足而崩溃。这正是算法设计中常见的规模扩展问题也是我们今天要探讨的核心。1. 问题分析与基础解法让我们先理解题目本质在一条长度为L的马路上初始每个整数点都有一棵树。给定M个区间需要移除这些区间内的所有树最后统计剩余树木数量。用编程术语来说这就是一个典型的区间覆盖统计问题。对于小规模数据如L≤10000最直观的解法是使用标记数组int trees[10001] {0}; // 初始化所有位置为0表示有树 for(int i 0; im; i){ scanf(%d%d, a, b); for(int ja; jb; j){ trees[j] 1; // 标记为1表示树被移除 } } int remaining 0; for(int i0; il; i){ if(trees[i] 0) remaining; }这种解法时间复杂度为O(M×L)当L10000、M100时运算量在百万级别现代计算机完全可以轻松处理。但问题在于当L10^9时需要约4GB内存假设int为4字节显然不现实即使内存足够O(M×L)的时间复杂度在M10^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 i1; ipoints.size(); i){ if(!is_removed(points[i-1], points[i])){ // 判断该区间是否被任何原始区间覆盖 result points[i] - points[i-1] -1; // 计算区间内树的数量 } }离散化将复杂度从O(L)降到了O(M log M)因为主要开销在于排序。这使得处理L10^9、M10^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-l1, false, nullptr, nullptr}; if(l ! r) { int mid (l r) / 2; node-leftChild build(l, mid); node-rightChild build(mid1, 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; } } };这种灵活性使得线段树成为算法竞赛和工程开发中的重要工具。