download：图灵学院 JAVA 高级架构师【第四期】最新完结无密
线段树（动静开点）的两种形式
题目描述
Tag :「线段树（动静开点）」、「线段树」
实现一个 MyCalendar 类来存放你的日程安排。如果要增加的工夫内不会导致三重预订时，则可能存储这个新的日程安排。
MyCalendar 有一个 book(int start, int end) 方法。它意味着在 start 到 end 工夫内减少一个日程安排，注意，这里的工夫是半开区间，即 [start,end)[start, end)[start,end), 实数 xxx 的范畴为，start<=x<end start <= x < end start<=x<end。
当三个日程安排有一些工夫上的交叉时（例如三个日程安排都在同一时间内），就会产生三重预订。
每次调用 MyCalendar.book 方法时，如果可能将日程安排胜利增加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排增加到日历中。
请按照以下步骤调用 MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
示例：
MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); // returns true
解释：
前两个日程安排可能增加至日历中。第三个日程安排会导致双重预订，但可能增加至日历中。
第四个日程安排流动（5,15）不能增加至日历中，因为它会导致三重预订。
第五个日程安排（5,10）可能增加至日历中，因为它未使用已经双重预订的工夫 10。
第六个日程安排（25,55）可能增加至日历中，因为工夫 [25,40] 将和第三个日程安排双重预订；
工夫 [40,50] 将独自预订，工夫 [50,55）将和第二个日程安排双重预订。复制代码
提醒：
每个测试用例，调用 MyCalendar.book 函数最多不超过 100010001000 次。
调用函数 MyCalendar.book(start, end) 时，start 和 end 的取值范畴为 0,109[0,109]。
线段树（动静开点）- 估点
和 729. 我的日程安排表 I 几乎残缺一致，只需要将对「线段树」所保护的节点信息进行调整即可。
线段树保护的节点信息包含：
ls/rs: 别离代表以后节点的左右子节点在线段树数组 tr 中的下标；
add: 懒标记；
max: 为以后区间的最大值。
对于惯例的线段树实现来说，都是一开始就调用 build 操作创建空树，而线段树一般以「满二叉树」的形式用数组存储，因此需要 4×n4 \times n4×n 的空间，并且这些空间在起始 build 空树的时候已经锁死。
如果一道题仅仅是「值域很大」的离线题（提前通晓所有的询问），咱们还能通过「离散化」来进行处理，将值域映射到一个小空间去，从而解决 MLE 问题。
但对于本题而言，因为「强制在线」的原因，咱们无奈进行「离散化」，同时值域大小达到 1e91e91e9 级别，因此如果咱们想要使用「线段树」进行求解，只能采取「动静开点」的形式进行。
动静开点的劣势在于，不需要事先构造空树，而是在插入操作 add 和查问操作 query 时根据拜访需要进行「开点」操作。因为咱们不保障查问和插入都是间断的，因此对于父节点 uuu 而言，咱们不能通过 u << 1 和 u << 1 | 1 的固定形式进行拜访，而要将节点 tr[u]tr[u]tr[u] 的左右节点所在 tr 数组的下标进行存储，别离记为 ls 和 rs 属性。对于 tr[u].ls=0tr[u].ls = 0tr[u].ls=0 和 tr[u].rs=0tr[u].rs = 0tr[u].rs=0 则是代表子节点尚未被创建，当需要拜访到它们，而又尚未创建的时候，则将其进行创建。
因为存在「懒标记」，线段树的插入和查问都是 logn\log{n}logn 的，因此咱们在单次操作的时候，最多会创建数量级为 logn\log{n}logn 的点，因此空间复杂度为 O(mlogn)O(m\log{n})O(mlogn)，而不是 O(4×n)O(4 \times n)O(4×n)，而开点数的预估需不能仅仅根据 logn\log{n}logn 来进行，还要对常熟进行分析，才能失去准确的点数上界。
动静开点相比于原始的线段树实现，本质仍是使用「满二叉树」的形式进行存储，只不过是按需创建区间，如果咱们是按照间断段进行查问或插入，最坏情况下仍然会占到 4×n4 \times n4×n 的空间，因此盲猜 logn\log{n}logn 的常数在 444 左右，激进一点可能间接估算到 666，因此咱们可能估算点数为 6×m×logn6 \times m \times \log{n}6×m×logn，其中 n=1e9n = 1e9n=1e9 和 m=1e3m = 1e3m=1e3 别离代表值域大小和查问次数。
当然一个比较实用的估点形式可能「尽可能的多开点数」，利用题目给定的空间上界和咱们创建的自定义类（结构体）的大小，尽可能的多开（Java 的 128M128M128M 可能开到 5×1065 \times 10^65×106 以上）。
Java 代码：
class MyCalendarTwo {
class Node {int ls, rs, add, max;}
int N = (int)1e9, M = 120010, cnt = 1;
Node[] tr = new Node[M];
void update(int u, int lc, int rc, int l, int r, int v) {if (l <= lc && rc <= r) {tr[u].add += v;
tr[u].max += v;
return ;
}
lazyCreate(u);
pushdown(u);
int mid = lc + rc >> 1;
if (l <= mid) update(tr[u].ls, lc, mid, l, r, v);
if (r > mid) update(tr[u].rs, mid + 1, rc, l, r, v);
pushup(u);
}
int query(int u, int lc, int rc, int l, int r) {if (l <= lc && rc <= r) return tr[u].max;
lazyCreate(u);
pushdown(u);
int mid = lc + rc >> 1, ans = 0;
if (l <= mid) ans = Math.max(ans, query(tr[u].ls, lc, mid, l, r));
if (r > mid) ans = Math.max(ans, query(tr[u].rs, mid + 1, rc, l, r));
return ans;
}
void lazyCreate(int u) {if (tr[u] == null) tr[u] = new Node();
if (tr[u].ls == 0) {tr[u].ls = ++cnt;
tr[tr[u].ls] = new Node();}
if (tr[u].rs == 0) {tr[u].rs = ++cnt;
tr[tr[u].rs] = new Node();}
}
void pushup(int u) {tr[u].max = Math.max(tr[tr[u].ls].max, tr[tr[u].rs].max);
}
void pushdown(int u) {tr[tr[u].ls].add += tr[u].add; tr[tr[u].rs].add += tr[u].add;
tr[tr[u].ls].max += tr[u].add; tr[tr[u].rs].max += tr[u].add;
tr[u].add = 0;
}
public boolean book(int start, int end) {if (query(1, 1, N + 1, start + 1, end) >= 2) return false;
update(1, 1, N + 1, start + 1, end, 1);
return true;
}}
复制代码
TypeScript 代码：
class TNode {
ls: number = 0; rs: number = 0
max:number = 0; add: number = 0; }
class MyCalendarTwo {
N = 1e9; M = 120010; cnt = 1
tr: TNode[] = new Array<TNode>(this.M)
query(u: number, lc: number, rc: number, l: number, r: number): number {if (l <= lc && rc <= r) return this.tr[u].max;
this.pushdown(u)
let mid = lc + rc >> 1, ans = 0
if (l <= mid) ans = Math.max(ans, this.query(this.tr[u].ls, lc, mid, l, r))
if (r > mid) ans = Math.max(ans, this.query(this.tr[u].rs, mid + 1, rc, l, r))
return ans
}
update(u: number, lc: number, rc: number, l: number, r: number, v: number): number {if (l <= lc && rc <= r) {this.tr[u].add += v
this.tr[u].max += v
return
}
this.pushdown(u)
let mid = lc + rc >> 1
if (l <= mid) this.update(this.tr[u].ls, lc, mid, l, r, v)
if (r > mid) this.update(this.tr[u].rs, mid + 1, rc, l, r, v)
this.pushdup(u)
}
pushdown(u: number): void {if (this.tr[u] == null) this.tr[u] = new TNode()
if (this.tr[u].ls == 0) {this.tr[u].ls = ++this.cnt
this.tr[this.tr[u].ls] = new TNode()}
if (this.tr[u].rs == 0) {this.tr[u].rs = ++this.cnt
this.tr[this.tr[u].rs] = new TNode()}
const add = this.tr[u].add
this.tr[this.tr[u].ls].add += add; this.tr[this.tr[u].rs].add += add
this.tr[this.tr[u].ls].max += add; this.tr[this.tr[u].rs].max += add
this.tr[u].add = 0
}
pushdup(u: number): void {this.tr[u].max = Math.max(this.tr[this.tr[u].ls].max, this.tr[this.tr[u].rs].max)
}
book(start: number, end: number): boolean {if (this.query(1, 1, this.N + 1, start + 1, end) >= 2) return false
this.update(1, 1, this.N + 1, start + 1, end, 1)
return true
}}
复制代码
工夫复杂度：令 nnn 为值域大小，本题固定为 1e91e91e9，线段树的查问和减少复杂度均为 O(logn)O(\log{n})O(logn)
空间复杂度：令询问数量为 mmm，复杂度为 O(mlogn)O(m\log{n})O(mlogn)
线段树（动静开点）- 动静指针
利用「动静指针」实现的「动静开点」可能无效避免数组估点问题，更重要的是可能无效避免 new 大数组的初始化开销，对于 LC 这种还跟你算所有样例总时长的 OJ 来说，在不考虑 static 优化 / 全局数组优化 的情况下，动静指针的形式要比估点的形式来得好。
Java 代码：
class MyCalendarTwo {
class Node {
Node ls, rs;
int max, add;
}
int N = (int)1e9;
Node root = new Node();
void update(Node node, int lc, int rc, int l, int r, int v) {if (l <= lc && rc <= r) {
node.add += v;
node.max += v;
return ;
}
pushdown(node);
int mid = lc + rc >> 1;
if (l <= mid) update(node.ls, lc, mid, l, r, v);
if (r > mid) update(node.rs, mid + 1, rc, l, r, v);
pushup(node);
}
int query(Node node, int lc, int rc, int l, int r) {if (l <= lc && rc <= r) return node.max;
pushdown(node);
int mid = lc + rc >> 1, ans = 0;
if (l <= mid) ans = query(node.ls, lc, mid, l, r);
if (r > mid) ans = Math.max(ans, query(node.rs, mid + 1, rc, l, r));
return ans;
}
void pushdown(Node node) {if (node.ls == null) node.ls = new Node();
if (node.rs == null) node.rs = new Node();
int add = node.add;
node.ls.max += add; node.rs.max += add;
node.ls.add += add; node.rs.add += add;
node.add = 0;
}
void pushup(Node node) {node.max = Math.max(node.ls.max, node.rs.max);
}
public boolean book(int start, int end) {if (query(root, 0, N, start, end - 1) >= 2) return false;
update(root, 0, N, start, end - 1, 1);
return true;
}}
复制代码
TypeScript 代码：
class TNode {
ls: TNode = null; rs: TNode = null
max: number = 0; add: number = 0}
class MyCalendarTwo {
root: TNode = new TNode()
update(node: TNode, lc: number, rc: number, l: number, r: number, v: number): void {if (l <= lc && rc <= r) {
node.add += v
node.max += v
return
}
this.pushdown(node)
let mid = lc + rc >> 1
if (l <= mid) this.update(node.ls, lc, mid, l, r, v)
if (r > mid) this.update(node.rs, mid + 1, rc, l, r, v)
this.pushup(node)
}
query(node: TNode, lc: number, rc: number, l: number, r: number): number {if (l <= lc && rc <= r) return node.max
let mid = lc + rc >> 1, ans = 0
this.pushdown(node)
if (l <= mid) ans = this.query(node.ls, lc, mid, l, r)
if (r > mid) ans = Math.max(ans, this.query(node.rs, mid + 1, rc, l, r))
return ans
}
pushdown(node: TNode): void {if (node.ls == null) node.ls = new TNode()
if (node.rs == null) node.rs = new TNode()
const add = node.add
node.ls.add += add; node.rs.add += add
node.ls.max += add; node.rs.max += add
node.add = 0
}
pushup(node: TNode): void {node.max = Math.max(node.ls.max, node.rs.max)
}
book(start: number, end: number): boolean {if (this.query(this.root, 0, 1e9, start, end - 1) >= 2) return false
this.update(this.root, 0, 1e9, start, end - 1, 1)
return true
}}
复制代码
工夫复杂度：令 nnn 为值域大小，本题固定为 1e91e91e9，线段树的查问和减少复杂度均为 O(logn)O(\log{n})O(logn)
空间复杂度：令询问数量为 mmm，复杂度为 O(mlogn)O(m\log{n})O(mlogn)