刷题前唠嗑
LeetCode? 启动！！！
嗯？怎么是 hard，好长，可恶，看不懂，怎么办
题目：Range 模块
题目链接：715. Range 模块
题目描述
代码与解题思路
今天是个好日子（毕竟是周日），必须露两手，来看代码：
const N int = 1e9
type node struct {
lch *node
rch *node
added bool
lazy int
}
type segmentTree struct {
root *node
}
func newSegmentTree() *segmentTree {
return &segmentTree{
root: new(node),
}
}
func (t *segmentTree) update(n *node, l, r, i, j, x int) {
if l >= i && r <= j {
n.added = x == 1
n.lazy = x
return
}
t.pushdown(n)
m := int(uint(l+r) >> 1)
if i <= m {
t.update(n.lch, l, m, i, j, x)
}
if j > m {
t.update(n.rch, m+1, r, i, j, x)
}
t.pushup(n)
}
func (t *segmentTree) query(n *node, l, r, i, j int) bool {
if l >= i && r <= j {
return n.added
}
t.pushdown(n)
v := true
m := int(uint(l+r) >> 1)
if i <= m {
v = v && t.query(n.lch, l, m, i, j)
}
if j > m {
v = v && t.query(n.rch, m+1, r, i, j)
}
return v
}
func (t *segmentTree) pushup(n *node) {
n.added = n.lch.added && n.rch.added
}
func (t *segmentTree) pushdown(n *node) {
if n.lch == nil {
n.lch = new(node)
}
if n.rch == nil {
n.rch = new(node)
}
if n.lazy != 0 {
n.lch.added = n.lazy == 1
n.rch.added = n.lazy == 1
n.lch.lazy = n.lazy
n.rch.lazy = n.lazy
n.lazy = 0
}
}
type RangeModule struct {
t *segmentTree
}
func Constructor() RangeModule {
return RangeModule{
t: newSegmentTree(),
}
}
func (this *RangeModule) AddRange(left int, right int) {
this.t.update(this.t.root, 1, N, left, right-1, 1)
}
func (this *RangeModule) QueryRange(left int, right int) bool {
return this.t.query(this.t.root, 1, N, left, right-1)
}
func (this *RangeModule) RemoveRange(left int, right int) {
this.t.update(this.t.root, 1, N, left, right-1, -1)
}
/**
* Your RangeModule object will be instantiated and called as such:
* obj := Constructor();
* obj.AddRange(left,right);
* param_2 := obj.QueryRange(left,right);
* obj.RemoveRange(left,right);
*/
只需要 5 秒，来看解题流程：
- 打开一份大佬题解
- CTRL + C
- CTRL + V
- 提交代码
- 过啦
。。。
今天是线段树，真不会，没办法，只好使用 CV 大法了