【LeetCode: 2276. 统计区间中的整数数目 | 线段树】

2023-12-16 12:46:30

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样?
🌲 作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

在这里插入图片描述

在这里插入图片描述

🚩 题目链接

? 题目描述

给你区间的 空 集,请你设计并实现满足要求的数据结构:

新增:添加一个区间到这个区间集合中。
统计:计算出现在 至少一个 区间中的整数个数。
实现 CountIntervals 类:

CountIntervals() 使用区间的空集初始化对象
void add(int left, int right) 添加区间 [left, right] 到区间集合之中。
int count() 返回出现在 至少一个 区间中的整数个数。
注意:区间 [left, right] 表示满足 left <= x <= right 的所有整数 x 。

示例 1:

输入
[“CountIntervals”, “add”, “add”, “count”, “add”, “count”]
[[], [2, 3], [7, 10], [], [5, 8], []]
输出
[null, null, null, 6, null, 8]

解释
CountIntervals countIntervals = new CountIntervals(); // 用一个区间空集初始化对象
countIntervals.add(2, 3); // 将 [2, 3] 添加到区间集合中
countIntervals.add(7, 10); // 将 [7, 10] 添加到区间集合中
countIntervals.count(); // 返回 6
// 整数 2 和 3 出现在区间 [2, 3] 中
// 整数 7、8、9、10 出现在区间 [7, 10] 中
countIntervals.add(5, 8); // 将 [5, 8] 添加到区间集合中
countIntervals.count(); // 返回 8
// 整数 2 和 3 出现在区间 [2, 3] 中
// 整数 5 和 6 出现在区间 [5, 8] 中
// 整数 7 和 8 出现在区间 [5, 8] 和区间 [7, 10] 中
// 整数 9 和 10 出现在区间 [7, 10] 中

提示:

1 <= left <= right <= 109
最多调用 add 和 count 方法 总计 105 次
调用 count 方法至少一次

🌟 求解思路&实现代码&运行结果


? 线段树

🥦 求解思路
  1. 该题目直接通过线段树模板来求解即可,但是一定要弄明白各个参数的含义。
  2. 实现代码如下所示:
🥦 实现代码 - 线段树
class CountIntervals {

    public CountIntervals() {

    }
    
    public void add(int left, int right) {
        update(1,1,N+1,left,right,1);
    }
    
    public int count() {
        return query(1,1,N+1,1,N);
    }

    class Node {
        int ls, rs, add, val;
    }

    int N=(int)1e9,M=1200010,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].val=(rc-lc+1)*v;
            tr[u].add=v;
            return;
        }
        lazyCreate(u);
        pushdown(u, rc-lc+1);
        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].val;
        }
        lazyCreate(u);
        pushdown(u, rc-lc+1);
        int mid=lc+rc>>1,ans=0;
        if(l<=mid) ans=query(tr[u].ls, lc, mid, l, r);
        if(r>mid) 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 pushdown(int u,int len) {
        if(tr[u].add==0) return;
        tr[tr[u].ls].add=tr[u].add;
        tr[tr[u].rs].add=tr[u].add;
        tr[tr[u].ls].val=(len-len/2)*tr[u].add;
        tr[tr[u].rs].val=(len/2)*tr[u].add;
        tr[u].add=0;
    }

    void pushup(int u) {
        tr[u].val=tr[tr[u].ls].val+tr[tr[u].rs].val;
    }
    
}



/**
 * Your CountIntervals object will be instantiated and called as such:
 * CountIntervals obj = new CountIntervals();
 * obj.add(left,right);
 * int param_2 = obj.count();
 */
🥦 运行结果

在这里插入图片描述


💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

在这里插入图片描述

在这里插入图片描述

文章来源:https://blog.csdn.net/Coder_ljw/article/details/135029368
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。