当前位置：网站首页>【线段树实战】最近的请求次数 + 区域和检索 - 数组可修改+我的日程安排表Ⅰ/Ⅲ

【线段树实战】最近的请求次数 + 区域和检索 - 数组可修改+我的日程安排表Ⅰ/Ⅲ

2022-07-06 22:03:00 【爱写Bug的王六六】

之前写的文章：在语雀上写的线段树解析以及题目实战
线段树模板：

/** * 线段树（动态开点） **/
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;
        // 对区间进行「加减」的更新操作，下推懒惰标记时需要累加起来，不能直接覆盖
        node.left.add += node.add;
        node.right.add += node.add;
        node.add = 0;
    }
}

● 对于表示为「区间和」且对区间进行「加减」的更新操作的情况，在更新节点值的时候『需要️左右孩子区间叶子节点的数量』；我们在下推懒惰标记的时候『需要累加』(这种情况和模版一致) 如题目 最近的请求次数
● 对于表示为「区间和」且对区间进行「覆盖」的更新操作的情况，我们在更新节点值的时候『需要️左右孩子区间叶子节点的数量』；我们在下推懒惰标记的时候『不需要累加』！！(因为是覆盖操作！！) 如题目 307. 区域和检索 - 数组可修改
● 对于表示为「区间最值」 且对区间进行「加减」的更新操作的情况，我们在更新节点值的时候『不需要️左右孩子区间叶子节点的数量』；我们在下推懒惰标记的时候『需要累加』！！ 如题目 我的日程安排表 I、 我的日程安排表 III

注意：
对于题目 最近的请求次数 和 307. 区域和检索 - 数组可修改 可以「不用️左右孩子区间叶子节点的数量」
为什么？？因为这两个题目是「点更新」，在介绍线段树更新的时候：「点更新」和「区间更新」可以合并成一种，「点更新」就是更新长度为 1 的区间嘛。
上面两个题目调用更新函数的方式为：

  • update(root, 1, N, t, t, 1);
  • update(root, 0, N, i, i, nums[i]);

由于区间是一个点，所以一定会更新到叶子节点，故可以不用️左右孩子区间叶子节点的数量！！

最近的请求次数

在这里插入图片描述
代码实现：

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);
    }
 
    // *************** 下面是模版 ***************
    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 += 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;
        // 对区间进行「加减」的更新操作，下推懒惰标记时需要累加起来，不能直接覆盖
        node.left.add += node.add;
        node.right.add += node.add;
        node.add = 0;
    }
}

307. 区域和检索 - 数组可修改

在这里插入图片描述

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);
    }
 	//***********下面是模板****************
    class Node {
    
        // 左右孩子节点
        Node left, right;
        // 当前节点值，以及懒惰标记的值
        int val, add;
    }
    private int N;
    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;
        node.left.add = node.add;
        node.right.add = node.add;
        node.add = 0;
    }
}

我的日程安排表 III

在这里插入图片描述

「节点的值不止可以表示该区间的和」，还可以「表示为当前区间的最值」，该题目存储的就是区间的最大值
代码：

class MyCalendarThree {
    
 
    public MyCalendarThree() {
    
 
    }
    
    public int book(int start, int end) {
    
        // 只用到了 update
        update(root, 0, N, start, end - 1, 1);
        // 最大值即为根节点的值
        return root.val;
    }
    // *************** 下面是模版 ***************
    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 += 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) {
    
        // 每个节点存的是当前区间的最大值
        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;
    }
}

我的日程安排表 I

在这里插入图片描述
根据Ⅲ的解题思路：

class MyCalendar {
    

    public MyCalendar() {
    

    }
    
    public boolean book(int start, int end) {
    
        // 先查询该区间是否为 0
        if (query(root, 0, N, start, end - 1) != 0) return false;
        // 更新该区间
        update(root, 0, N, start, end - 1, 1);
        return true;
    }
    // *************** 下面是模版 ***************
    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 += 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) {
    
        // 每个节点存的是当前区间的最大值
        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;
    }
}
原网站

版权声明
本文为[爱写Bug的王六六]所创，转载请带上原文链接，感谢
https://blog.csdn.net/m0_58058653/article/details/125640031

边栏推荐

猜你喜欢

随机推荐