大前端2022版全面升级某课完结大前端

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: 为当前区间的最大值。
【大前端2022版全面升级某课完结】关于常规的线段树完成来说，都是一开端就调用 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(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(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 }

}
复制代码
时间复杂度：令 nnn 为值域大小，本题固定为 1e91e91e9，线段树的查询和增加复杂度均为 O(log?n)O(\log{n})O(logn)
空间复杂度：令讯问数量为 mmm，复杂度为 O(mlog?n)O(m\log{n})O(mlogn)