当前位置:网站首页>[line segment tree practice] recent requests + area and retrieval - array modifiable + my schedule I / III
[line segment tree practice] recent requests + area and retrieval - array modifiable + my schedule I / III
2022-07-07 04:39:00 【Wang Liuliu, who loves to write bugs】
Previous articles : Line segment tree analysis and topic practice written on YuQue
Line tree template :
/** * Line segment tree ( Dynamic opening point ) **/
public class SegmentTreeDynamic {
// Segment tree data structure
class Node {
Node left, right;
int val, add;
}
private int N = (int) 1e9;
// First create the first node
private Node root = new Node();
// to update
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);
// Update left and right intervals
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);
}
// Inquire about
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;
}
// Update the node value up
private void pushUp(Node node) {
node.val = node.left.val + node.right.val;
}
// Push down
private void pushDown(Node node, int leftNum, int rightNum) {
// If there are no left and right nodes, create a new
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;
}
}
● For, expressed as 「 Interval and 」 And the interval is 「 Addition and subtraction 」 Update operation of , When updating node values 『 need ️ Left and right child interval Leaf node The number of 』; When we push down the lazy tag 『 Need to add up 』( This situation is consistent with the template ) Such as title Recent requests
● For, expressed as 「 Interval and 」 And the interval is 「 Cover 」 Update operation of , When we update the node value 『 need ️ Left and right child interval Leaf node The number of 』; When we push down the lazy tag 『 There is no need to add up 』!!( Because it is an override operation !!) Such as title 307. Area and retrieval - Array can be modified
● For, expressed as 「 The best value of the interval 」 And the interval is 「 Addition and subtraction 」 Update operation of , When we update the node value 『 Unwanted ️ The number of leaf nodes in the left and right child intervals 』; When we push down the lazy tag 『 Need to add up 』!! Such as title My schedule I、 My schedule III
Be careful :
For the title Recent requests and 307. Area and retrieval - Array can be modified Sure 「 no need ️ The number of leaf nodes in the left and right child intervals 」
Why? ?? Because these two topics are 「 Click Update 」, When introducing the update of line segment tree :「 Click Update 」 and 「 Interval update 」 Can be merged into one ,「 Click Update 」 The update length is 1 The range of .
The above two questions call Update function By :
- update(root, 1, N, t, t, 1);
- update(root, 0, N, i, i, nums[i]);
Because the interval is a point , So it must be updated to the leaf node , So you don't have to ️ The number of leaf nodes in the left and right child intervals !!
Recent requests
Code implementation :
class RecentCounter {
public RecentCounter() {
}
public int ping(int t) {
update(root, 1, N, t, t, 1);
return query(root, 1, N, Math.max(0, t - 3000), t);
}
// *************** 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 ;
}
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;
}
}
307. Area and retrieval - Array can be modified
class NumArray {
public NumArray(int[] nums) {
N = nums.length - 1;
for (int i = 0; i <= N; i++) {
update(root, 0, N, i, i, nums[i]);
}
}
public void update(int index, int val) {
update(root, 0, N, index, index, val);
}
public int sumRange(int left, int right) {
return query(root, 0, N, left, right);
}
//*********** Here's 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;
private Node root = new Node();
// to update
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);
}
// Inquire about
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;
}
// Up
private void pushUp(Node node) {
node.val = node.left.val + node.right.val;
}
// Down
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;
node.left.add = node.add;
node.right.add = node.add;
node.add = 0;
}
}
My schedule III
「 The value of a node can represent more than the sum of the interval 」, just so so 「 Expressed as the maximum value of the current interval 」, The storage of this topic is interval Maximum
Code :
class MyCalendarThree {
public MyCalendarThree() {
}
public int book(int start, int end) {
// It's only used. update
update(root, 0, N, start, end - 1, 1);
// The maximum value is the value of the root node
return root.val;
}
// *************** 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;
}
}
My schedule I
according to Ⅲ How to solve the problem :
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;
}
}
边栏推荐
- SSM+JSP实现企业管理系统(OA管理系统源码+数据库+文档+PPT)
- Network Security Learning - Information Collection
- Golang calculates constellations and signs based on birthdays
- Detect when a tab bar item is pressed
- System framework of PureMVC
- 浙江大学周亚金:“又破又立”的顶尖安全学者,好奇心驱动的行动派
- Two divs are on the same line, and the two divs do not wrap "recommended collection"
- [team learning] [34 issues] scratch (Level 2)
- 日常工作中程序员最讨厌哪些工作事项?
- Video fusion cloud platform easycvr video Plaza left column list style optimization
猜你喜欢
SSM+JSP实现企业管理系统(OA管理系统源码+数据库+文档+PPT)
MySQL forgot how to change the password
[ArcGIS tutorial] thematic map production - population density distribution map - population density analysis
Dab-detr: dynamic anchor boxes are better queries for Detr translation
Continuous learning of Robotics (Automation) - 2022-
[team learning] [phase 34] Baidu PaddlePaddle AI talent Creation Camp
Introduction to the PureMVC series
Digital chemical plant management system based on Virtual Simulation Technology
EasyCVR集群重启导致其他服务器设备通道状态离线情况的优化
How to solve the problem of adding RTSP device to easycvr cluster version and prompting server ID error?
随机推荐
Highly paid programmers & interview questions. Are you familiar with the redis cluster principle of series 120? How to ensure the high availability of redis (Part 1)?
Detect when a tab bar item is pressed
程序员上班摸鱼,这么玩才高端!
Common methods of list and map
What about the collapse of win11 playing pubg? Solution to win11 Jedi survival crash
【实践出真理】import和require的引入方式真的和网上说的一样吗
NanopiNEO使用开发过程记录
The worse the AI performance, the higher the bonus? Doctor of New York University offered a reward for the task of making the big model perform poorly
How to conduct website testing of software testing? Test strategy let's go!
Advertising attribution: how to measure the value of buying volume?
论文上岸攻略 | 如何快速入门学术论文写作
What is CGI, IIS, and VPS "suggested collection"
A detailed explanation of head pose estimation [collect good articles]
Lecture 3 of "prime mover x cloud native positive sounding, cost reduction and efficiency enhancement lecture" - kubernetes cluster utilization improvement practice
一度辍学的数学差生,获得今年菲尔兹奖
日常工作中程序员最讨厌哪些工作事项?
一图看懂!为什么学校教了你Coding但还是不会的原因...
Introduction to the PureMVC series
Thesis landing strategy | how to get started quickly in academic thesis writing
Golang calculates constellations and signs based on birthdays