download：前端工程师2022版某课完结
线段树（动态开点）的两种方式
标题描绘
Tag : 「线段树（动态开点）」、「线段树」
完成一个 MyCalendar 类来寄存你的日程布置。假如要添加的时间内不会招致三重预订时，则能够存储这个新的日程布置。
MyCalendar 有一个 book(int start, int end) 办法。它意味着在 start 到 end 时间内增加一个日程布置，留意，这里的时间是半开区间，即 [start,end)[start, end)[start,end), 实数 xxx 的范围为， start<=x
每次调用 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 则是代表子节点尚未被创立，当需求访问到它们，而又尚未创立的时分，则将其停止创立。
由于存在「懒标志」，线段树的插入和查询都是 log?n\log{n}logn 的，因而我们在单次操作的时分，最多会创立数量级为 log?n\log{n}logn 的点，因而空间复杂度为 O(mlog?n)O(m\log{n})O(mlogn)，而不是 O(4×n)O(4 \times n)O(4×n)，而开点数的预估需不能仅仅依据 log?n\log{n}logn 来停止，还要对常熟停止剖析，才干得到精确的点数上界。
动态开点相比于原始的线段树完成，实质仍是运用「满二叉树」的方式停止存储，只不过是按需创立区间，假如我们是依照连续段停止查询或插入，最坏状况下依然会占到 4×n4 \times n4×n 的空间，因而盲猜 log?n\log{n}logn 的常数在 444 左右，激进一点能够直接预算到 666，因而我们能够预算点数为 6×m×log?n6 \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
}
复制代码
时间复杂度：令 nnn 为值域大小，本题固定为 1e91e91e9，线段树的查询和增加复杂度均为 O(log?n)O(\log{n})O(logn)
空间复杂度：令讯问数量为 mmm，复杂度为 O(mlog?n)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
}
}
复制代码
【前端工程师2022版某课完结】时间复杂度：令 nnn 为值域大小，本题固定为 1e91e91e9，线段树的查询和增加复杂度均为 O(log?n)O(\log{n})O(logn)
空间复杂度：令讯问数量为 mmm，复杂度为 O(mlog?n)O(m\log{n})O(mlogn)
