本文主要是介绍LeetCode 2276. 统计区间中的整数数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目
1、题目描述
给你区间的 空 集，请你设计并实现满足要求的数据结构：
- 新增：添加一个区间到这个区间集合中。
- 统计：计算出现在 至少一个 区间中的整数个数。
实现
CountIntervals类：
CountIntervals()使用区间的空集初始化对象void add(int left, int right)添加区间[left, right]到区间集合之中。int count()返回出现在 至少一个 区间中的整数个数。注意：区间
[left, right]表示满足left <= x <= right的所有整数x
2、接口描述
class CountIntervals {
public:CountIntervals() {}void add(int left, int right) {}int count() {}
};/*** Your CountIntervals object will be instantiated and called as such:* CountIntervals* obj = new CountIntervals();* obj->add(left,right);* int param_2 = obj->count();*/3、原题链接
2276. 统计区间中的整数数目
二、解题报告
1、思路分析
对于区间维护问题，我们可以用线段树轻松解决。由于数据量很大，我们用动态开点的话，会导致爆内存，所以这里采用动态开点线段树，即用即开。
关于线段树的知识见：高级搜索-线段树[C/C++]-CSDN博客
2、复杂度
时间复杂度：O(nlogn) 空间复杂度：O(nlogn)
3、代码详解
class CountIntervals {
public:
CountIntervals* left = nullptr , * right = nullptr;
int l , r , sum = 0;CountIntervals():l(1),r(1e9) {}CountIntervals(int _l , int _r):l(_l) ,r(_r){}void add(int L, int R) {if(sum == r - l + 1) return;if(L <= l && r <= R){sum = r - l + 1 ;return;}int mid = (l + r) >> 1;if(left == nullptr) left = new CountIntervals(l,mid);if(right == nullptr) right = new CountIntervals(mid+1,r);if(L <= mid) left -> add(L , R);if(R > mid) right -> add(L , R);sum = left -> sum + right -> sum;}int count() {return sum;}
};/*** Your CountIntervals object will be instantiated and called as such:* CountIntervals* obj = new CountIntervals();* obj->add(left,right);* int param_2 = obj->count();*/这篇关于LeetCode 2276. 统计区间中的整数数目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
