求线段树的区间更新的代码

Question

包括区间更新的全加
还有区间更新的指定值

Answer 1

liuyubobobo 2018-07-28 03:11:47

可以参考我的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上找了找，没有找到合适的例题。有时间我再仔细找找：）你也可以尝试在理解了上述区间更新代码的代码的基础上，试试自己实现一个区间加法的代码：）

加油！：）

• 提问者 Penguinbupt #1

  老师，可以在代码部分附上简单的解释么？
  还有在类的函数的参数意义？
  
  好像从上到下传递lazy tag？

• liuyubobobo 回复 提问者 Penguinbupt #2

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