1回答

liuyubobobo

2018-07-28

已采纳

可以参考我的Leetcode题解代码仓中的218号问题的代码。

Leetcode问题传送门：

英文版：https://leetcode.com/problems/the-skyline-problem/description/ 

中文版：https://leetcode-cn.com/problems/the-skyline-problem/description/ 

我的代码传送门：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0218-The-Skyline-Problem/cpp-0218/main.cpp 

在这个问题中，其实就是要在一个线段（地平线）上，不断更新某一段区间的值（在某一段区间有一个建筑），最终汇总得到问题的答案。

在我的代码中，首先定义了一棵线段树，支持区间更新操作。由于在问题中是“添加”建筑，我定义的提供给用户的public方法叫add，在add中实际调用私有的update方法。

在区间更新中，一个重要的优化是懒惰更新。这个方式的实现主要依靠lazy数组实现。lazy数组做的事情是存储每个节点尚未更新的值。所以，在update和query初始，每访问到一个节点，都要查询一下lazy数组中是否有尚未更新的值。如果有，则在此时进行真正的对这个节点进行更新（改变tree的值）。而update的后续过程，则只更新lazy数组的值。

如果理解了这个代码，对某个区间加上一定值的逻辑是极其类似的。我简单在Leetcode上找了找，没有找到合适的例题。有时间我再仔细找找：）你也可以尝试在理解了上述区间更新代码的代码的基础上，试试自己实现一个区间加法的代码：）

加油！：）

0

2

liuyubobobo

回复

Penguinbupt

这里有一份很好的讲解，可以从 lazy propagation 的位置开始阅读：https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/

2021-06-11

共2条回复