优化:实现懒更新线段树
本文讲解的例题
LeetCode | 力扣 | 难度 |
---|---|---|
307. Range Sum Query - Mutable | 307. 区域和检索 - 数组可修改 | 🟠 |
线段树基本实现 中用数组和链表分别实现了线段树,文末留了两个优化点,分别是区间更新问题和稀疏数据的内存优化问题。
优化:动态线段树 解决了稀疏数据的内存优化问题,本文将基于 DynamicSegmentTree
的链式实现,使用「懒更新」技术,为线段树新增 rangeAdd/rangeUpdate
方法,在 时间复杂度内完成任意长度的区间更新。
本文实现的区间更新线段树和之前的单点更新线段树有几点区别:
1、因为单点更新可以看作是长度为 1 的区间更新,复杂度还是 ,所以我们不需要单独实现单点更新了。
2、我们不接受 merge
聚合函数了,因为涉及区间懒更新,如果同时考虑不同的聚合函数,会引入一些编程语言层面的细节问题,对于算法的学习没有什么意义,所以本文仅给出求和线段树的实现。如果你需要求最值等其他场景,可以自行修改代码中的聚合计算逻辑,或者使用文末提供的 AllInOneSegmentTree
万能模板。
3、线段树的区间更新可以是区间赋值(Assign),也可以区间累加(Increment)。
比方 [1, 2, 3, 4, 5]
这个数组,将索引区间 [1, 3]
内的元素都赋值为 10 叫做区间赋值,结果是 [1, 10, 10, 10, 5]
;将索引区间 [1, 3]
内的元素都增加 1 叫做区间累加,结果是 [1, 3, 4, 5, 5]
。
这两种场景都是算法题中常见的,本文会同时给出这两种实现。
我们之前实现的线段树主要 API 如下:
class SegmentTree {
// 初始化线段树
public SegmentTree(int[] nums, Function<Integer, Integer> merge) {}
// 查询闭区间 [qL, qR] 的聚合值,时间复杂度 O(logN)
public int query(int qL, int qR) {}
// 单点更新,设置 nums[i] = val,时间复杂度 O(logN)
public void update(int i, int val) {}
}
本文将实现以下两种线段树:
// 区间累加线段树
class IncrSegmentTree {
// 初始化动态线段树
public IncrSegmentTree(int start, int end, int defaultValue) {}
// 将闭区间 [qL, qR] 增加 delta(可以是负数),时间复杂度 O(logN)
public void rangeAdd(int qL, int qR, int delta) {}
// 查询闭区间 [qL, qR] 的元素和,时间复杂度 O(logN)
public int query(int qL, int qR) {}
}
// 区间赋值线段树
class AssignSegmentTree {
// 初始化动态线段树
public AssignSegmentTree(int start, int end, int defaultValue) {}
// 将闭区间 [qL, qR] 赋值为 val,时间复杂度 O(logN)
public void rangeUpdate(int qL, int qR, int val) {}
// 查询闭区间 [qL, qR] 的元素和,时间复杂度 O(logN)
public int query(int qL, int qR) {}
}
rangeAdd
和 rangeUpdate
的实现逻辑非常类似,理论上可以同时实现到一个类上,但是两个逻辑混在一起代码会更复杂,徒增理解成本,而且实际的算法题中,一般只会用到区间累加或区间赋值中的一种,不会同时用到,所以本文还是把它们拆到两个类分别实现,方便大家理解其原理。
本文的最后会给出一个万能线段树模板 AllInOneSegmentTree
,同时包含上述所有 API 和线段树的所有优化,笔试时可以直接拿来使用。