当前位置:网站首页>[daily question] 729 My schedule I
[daily question] 729 My schedule I
2022-07-06 06:51:00 【Wang Liuliu's it daily】
729. My schedule I
Reference resources : The blog post written by the boss in the effort to explain the topic ----- Line tree details 「 Summary level collation 」
Line tree series :
The segment tree solves 「 Interval and 」 The problem of , And the 「 Section 」 Will be modified .
Take a simple one , about nums = [1, 2, 3, 4, 5].
If we need to sum a certain interval many times , Did you first think of using 「 The prefix and 」.
The detailed introduction of prefix and can be seen Prefixes and arrays
nums = [1, 2, 3, 4, 5] The corresponding segment tree is as follows :
Each node represents an interval , And the value of the node is the sum of the interval .
- Sum of numbers 「 The sum of the total figures = The sum of the numbers in the left range + The sum of the numbers in the right range 」
- The greatest common factor (GCD)「 total GCD = gcd( Left interval GCD, The right range GCD)」
- Maximum 「 Total maximum = max( The maximum value of the left range , Maximum value in the right range )」
Data structure of segment tree
We can use arrays to represent a segment tree , Suppose the root node is i, Then the node of the left child is 2 * i, The node of the right child is 2 * i + 1 ( Premise :i from 1 Start )
We can use a linked list to represent a segment tree , The data structure of its nodes is as follows :
class Node {
// Left and right child nodes
Node left, right;
// Current node value
int val;
}
Prefer to use linked lists , Because it saves memory , The following implementations are based on linked lists .
Establishment of line segment tree
If a specific range is given in the title , We build a segment tree according to this range .
public void buildTree(Node node, int start, int end) {
// To the leaf node
if (start == end) {
node.val = arr[start];
return ;
}
int mid = (start + end) >> 1;
buildTree(node.left, start, mid);
buildTree(node.right, mid + 1, end);
// Update up
pushUp(node);
}
// Update up
private void pushUp(Node node) {
node.val = node.left.val + node.right.val;
}
But a lot of times , No specific scope is given in the title , Only the value range of data , It's usually big , So we often use 「 Dynamic opening point 」.
「 Dynamic opening point 」 Usually in 「 to update 」 or 「 Inquire about 」 Dynamically establish nodes when , See the following update and query operations for details .
Complete template of segment tree
Be careful : The following template is based on 「 Interval and 」 And the interval 「 Addition and subtraction 」 Update operation for , And for 「 Dynamic opening point 」
/** * @Description: Line segment tree ( Dynamic opening point ) * @Author: LFool * @Date 2022/6/7 09:15 **/
public class SegmentTreeDynamic {
class Node {
Node left, right;
int val, add;
}
private int N = (int) 1e9;
private Node root = new Node();
public void update(Node node, int start, int end, int l, int r, int val) {
if (l <= start && end <= r) {
node.val += (end - start + 1) * val;
node.add += val;
return ;
}
int mid = (start + end) >> 1;
pushDown(node, mid - start + 1, end - mid);
if (l <= mid) update(node.left, start, mid, l, r, val);
if (r > mid) update(node.right, mid + 1, end, l, r, val);
pushUp(node);
}
public int query(Node node, int start, int end, int l, int r) {
if (l <= start && end <= r) return node.val;
int mid = (start + end) >> 1, ans = 0;
pushDown(node, mid - start + 1, end - mid);
if (l <= mid) ans += query(node.left, start, mid, l, r);
if (r > mid) ans += query(node.right, mid + 1, end, l, r);
return ans;
}
private void pushUp(Node node) {
node.val = node.left.val + node.right.val;
}
private void pushDown(Node node, int leftNum, int rightNum) {
if (node.left == null) node.left = new Node();
if (node.right == null) node.right = new Node();
if (node.add == 0) return ;
node.left.val += node.add * leftNum;
node.right.val += node.add * rightNum;
// The interval is 「 Addition and subtraction 」 Update operation for , You need to add up when pushing down the lazy flag , Cannot directly cover
node.left.add += node.add;
node.right.add += node.add;
node.add = 0;
}
}
class MyCalendar {
public MyCalendar() {
}
public boolean book(int start, int end) {
// First query whether the interval is 0
if (query(root, 0, N, start, end - 1) != 0) return false;
// Update the interval
update(root, 0, N, start, end - 1, 1);
return true;
}
// *************** Here is the template ***************
class Node {
// Left and right child nodes
Node left, right;
// Current node value , And the value of the lazy tag
int val, add;
}
private int N = (int) 1e9;
private Node root = new Node();
public void update(Node node, int start, int end, int l, int r, int val) {
if (l <= start && end <= r) {
node.val += val;
node.add += val;
return ;
}
pushDown(node);
int mid = (start + end) >> 1;
if (l <= mid) update(node.left, start, mid, l, r, val);
if (r > mid) update(node.right, mid + 1, end, l, r, val);
pushUp(node);
}
public int query(Node node, int start, int end, int l, int r) {
if (l <= start && end <= r) return node.val;
pushDown(node);
int mid = (start + end) >> 1, ans = 0;
if (l <= mid) ans = query(node.left, start, mid, l, r);
if (r > mid) ans = Math.max(ans, query(node.right, mid + 1, end, l, r));
return ans;
}
private void pushUp(Node node) {
// Each node stores the maximum value of the current interval
node.val = Math.max(node.left.val, node.right.val);
}
private void pushDown(Node node) {
if (node.left == null) node.left = new Node();
if (node.right == null) node.right = new Node();
if (node.add == 0) return ;
node.left.val += node.add;
node.right.val += node.add;
node.left.add += node.add;
node.right.add += node.add;
node.add = 0;
}
}
/** * Your MyCalendar object will be instantiated and called as such: * MyCalendar obj = new MyCalendar(); * boolean param_1 = obj.book(start,end); */
边栏推荐
- PCL实现选框裁剪点云
- How to convert flv file to MP4 file? A simple solution
- Automated test environment configuration
- Classification des verbes reconstruits grammaticalement - - English Rabbit Learning notes (2)
- How much is it to translate Chinese into English for one minute?
- 机器人类专业不同层次院校课程差异性简述-ROS1/ROS2-
- 从autojs到冰狐智能辅助的心里历程
- 机器学习植物叶片识别
- Brief introduction to the curriculum differences of colleges and universities at different levels of machine human major -ros1/ros2-
- SSO process analysis
猜你喜欢
How effective is the Chinese-English translation of international economic and trade contracts
Huawei equipment configuration ospf-bgp linkage
Blue Bridge Cup zero Foundation National Championship - day 20
26岁从财务转行软件测试,4年沉淀我已经是25k的测开工程师...
What is the difference between int (1) and int (10)? Senior developers can't tell!
What are the commonly used English words and sentences about COVID-19?
How to reconstruct the class explosion caused by m*n strategies?
Today's summer solstice
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
E-book CHM online CS
随机推荐
Thesis abstract translation, multilingual pure human translation
Leetcode daily question (1870. minimum speed to arrive on time)
LeetCode每日一题(971. Flip Binary Tree To Match Preorder Traversal)
LeetCode - 152 乘积最大子数组
Latex文字加颜色的三种办法
Number of query fields
[ 英语 ] 语法重塑 之 动词分类 —— 英语兔学习笔记(2)
Day 245/300 JS foreach data cannot be updated to the object after multi-layer nesting
接口自动化测试实践指导(上):接口自动化需要做哪些准备工作
BUU的MISC(不定时更新)
接口自动化测试框架:Pytest+Allure+Excel
In English translation of papers, how to do a good translation?
详解SQL中Groupings Sets 语句的功能和底层实现逻辑
【刷题】怎么样才能正确的迎接面试?
How to reconstruct the class explosion caused by m*n strategies?
[ 英语 ] 语法重塑 之 英语学习的核心框架 —— 英语兔学习笔记(1)
[English] Verb Classification of grammatical reconstruction -- English rabbit learning notes (2)
Day 248/300 thoughts on how graduates find jobs
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Suspended else