A Simple Problem with Integers(线段树)

2017年10月12日560

题目链接

对问题的分析设计过程

题目要求对序列进行下列操作

  • 区间加法
  • 区间求和

因此可以考虑使用两个树状数组带懒标记维护的线段树来实现

程序中用到的数据机构和算法

该程序使用了带懒标记的线段树来实现上述操作。具体来说对线段树上的每个节点新增一个属性Lazy表示该区间被同时加上Lazy。在更新时若该节点区间被更新区间覆盖则直接更新Lazy,无需继续对其子节点进行修改。查询时在访问其儿子节点的同时将其Lazy下传至儿子节点。可证明单次修改以及查询其时间复杂度均为$O(\log n)$。总时间复杂度为$O(n+q\log n)$。 详细实现过程见代码。

程序的运行情况

该程序一共提交了3次,运行情况如下图所示:

错了两次的主要原因是因为对于lazy操作有点不太熟悉。

在实习过程中得到的经验和体会

线段树真的好用好写,在维护序列上强无敌。

Lazy操作需要考虑许许多多各种各样的方面需要小心一点

Code:

 

%d 博主赞过: