企业商城网站多少钱,靖江网站建设制作,郑州工商注册,河南工程建设信息网查OK#xff0c;今天来讲一讲线段树~~ 线段树是什么线段树的实现线段树的时间复杂度线段树的应用线段树的节点结构其他操作和优化例题——影子宽度输入输出格式输入格式输出格式 输入输出样例输入样例输出样例 例题讲解 线段树是什么
线段树#xff08; S e g m e n t Segmen…OK今天来讲一讲线段树~~ 线段树是什么线段树的实现线段树的时间复杂度线段树的应用线段树的节点结构其他操作和优化例题——影子宽度输入输出格式输入格式输出格式 输入输出样例输入样例输出样例 例题讲解 线段树是什么
线段树 S e g m e n t Segment Segment T r e e ~~Tree Tree是一种二叉树用于区间查询。线段树的每个节点表示一个区间根节点表示整个区间子节点表示区间的一半。线段树的典型应用是解决区间查询问题例如区间最大值、区间最小值等。
线段树的实现
线段树的构建过程可以通过递归实现。给定一个数组 a r r arr arr线段树的根节点表示 a r r [ 0 ] arr[0] arr[0]到 a r r [ n − 1 ] arr[n-1] arr[n−1]之间的区间和或其他区间操作。根节点的左子节点表示 a r r [ 0 ] arr[0] arr[0]到 a r r [ ( n − 1 ) / 2 ] arr[(n-1)/2] arr[(n−1)/2]之间的区间和右子节点表示 a r r [ ( n − 1 ) / 2 1 ] arr[(n-1)/21] arr[(n−1)/21]到 a r r [ n − 1 ] arr[n-1] arr[n−1]之间的区间和。依次类推直到区间被划分为长度为1的节点。
线段树的每个节点都会记录该节点表示的区间的一些统计信息例如区间和、区间最大值、区间最小值等。该统计信息可以通过节点的左子节点和右子节点的统计信息来计算得到。
当要查询的区间与当前节点表示的区间有重叠时查询操作会继续向下递归。当要查询的区间与当前节点表示的区间完全相等时查询操作可以直接返回当前节点的统计信息。当要查询的区间在当前节点表示的区间的左半部分时查询操作会向左子节点递归。当要查询的区间在当前节点表示的区间的右半部分时查询操作会向右子节点递归。
当要更新的位置在当前节点表示的区间内时更新操作会继续向下递归。当更新到叶子节点时将该位置的值更新为给定的新值。然后更新操作会向上递归将更新后的值传递给父节点并重新计算父节点的统计信息。
线段树的时间复杂度
线段树的时间复杂度为 O ( l o g ( n ) ) O(log(n)) O(log(n))其中n为数组的长度。这是因为构建线段树需要对每个节点进行一次操作总共需要 O ( n ) O(n) O(n)的时间。查询操作的时间复杂度为 O ( l o g ( n ) ) O(log(n)) O(log(n))因为查询的过程类似于二分查找每次将查询范围缩小一半最多需要递归 l o g ( n ) log(n) log(n)次。更新操作的时间复杂度也为 O ( l o g ( n ) ) O(log(n)) O(log(n))。
线段树是一种非常强大的数据结构可以用于解决各种区间查询问题。然而线段树的应用并不局限于时间复杂度为 O ( l o g ( n ) ) O(log(n)) O(log(n))的问题它还可以结合其他数据结构和算法来实现更高效的解决方案。例如线段树可以与离散化、树状数组等结合使用用于解决动态区间查询问题。同时线段树还可以用于解决一些特殊情况下的区间查询问题例如动态维护滑动窗口中的最大值、最小值等。
线段树的应用
线段树的应用非常广泛以下是一些常见的应用场景 区间最小值/最大值查询通过线段树可以在 O ( l o g ( n ) ) O(log(n)) O(log(n))的时间内找到任意区间的最小值或最大值。这在处理动态数据的情况下非常有用例如动态维护滑动窗口的最小值、最大值。 区间和查询线段树可以用来快速计算区间内所有元素的和。这在求解数组范围内的连续子数组和、处理区间加法或区间更新操作等问题非常有用。 区间更新线段树可以将区间内的某个值更新为新值。这在处理动态修改数据的情况下非常有用例如修改数组某个位置的值或者将区间内的所有元素增加某个固定值。 区间统计除了求和、最小值、最大值等基本操作外线段树还可以做更复杂的区间统计操作。例如可以通过线段树求解区间内的第 k k k小元素或者统计区间内有多少个不同的元素等。 离散化离散化是一种将连续的数据映射到离散的区间中的方法。通过使用线段树可以很方便地实现离散化操作将大量的连续数据映射到有限的离散区间内从而减小数据规模提高查询效率。 区间交集查询线段树可以用于判断两个区间是否有交集以及计算出两个区间的交集。这在处理区间重叠问题、查找共同区间等场景下非常有用。 区间覆盖查询线段树可以用于快速查找某个区间是否完全被覆盖以及计算出所有覆盖某个区间的区间。这在处理区间合并、区间分割等问题非常有用。
线段树是一种非常强大而灵活的数据结构可以根据需求进行扩展和优化。通过合理地设计数据结构和算法线段树可以高效地解决各种区间查询问题提高程序的性能和可扩展性。
线段树的节点结构
线段树的节点结构一般包含以下几个属性 start 和 end表示当前节点所代表的区间的起始和结束位置。 一个外挂依题目而定 其他操作和优化
线段树还可以进行一些其他的操作和优化例如
惰性更新使用标记来延迟更新减少更新操作的次数提高效率。区间增量维护区间值的增量而不是直接修改区间的值可以减少更新操作的次数。动态修改支持在原始数据的基础上进行修改而不需要重新构建整个线段树。
例题——影子宽度
精灵王的桌子上零散地放着若干个盒子桌子的后方是一堵墙。如下图所示。现在从桌子的前方射来一束平行光把盒子的影子投射到了墙上。问影子的总宽度是多少
输入输出格式
输入格式
第1行盒子的个数N1≤N≤10000。第2…N1行每个盒子的起始位置S和结束位置T1≤S, T≤100000。
输出格式
第1行包含一个整数表示影子的总宽度。
输入输出样例
输入样例
4
1 2
3 5
4 6
5 6输出样例
4例题讲解
这题纯纯版题呀
#include bits/stdc.h
using namespace std;
const int N120000;
int n,m,maxx,minn,a[N],b[N],cover[4*N];
void insert(int idx,int ll,int rr,int x,int y) {if (xll yrr) //如果区间范围包含当前线段cover[idx]1;if(cover[idx]1) //如果当前线段已经被标记了return;int mid(llrr)/2;if (ymid)insert(idx*2,ll,mid,x,y); //左子树递归else if (xmid)insert(idx*21,mid,rr,x,y); //右子树递归else { //拆分成两边分别递归insert(idx*2,ll,mid,x,y);insert(idx*21,mid,rr,x,y);}
}
int count(int idx,int ll,int rr,int x,int y) {if (cover[idx]1) //如果当前线段被标记return rr-ll; //返回长度if (rr-ll1) { //如果当前线段还是一个线段int mid(llrr)/2;int txcount(idx*2,ll,mid,x,y);int tycount(idx*21,mid,rr,x,y);return txty;}return 0;
}
int main() {scanf (%d,n);for (int i1;in;i) {scanf(%d%d,a[i],b[i]);if (a[i]maxx)maxxa[i];if (a[i]minn)minna[i];if (b[i]maxx)maxxb[i];if (b[i]minn)minnb[i];//一堆判断求最大边界和最小边界//有时候 是输入的数}for (int i1;in;i)insert(1,minn,maxx,a[i],b[i]); //标记线段printf(%d,count(1,minn,maxx,minn,maxx)); //输出结果return 0;
}
