[line segment tree practice] recent requests + area and retrieval - array modifiable + my schedule I / III

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;
    }
}