//线段树模板 偏执的太偏执、 2022-08-14 04:54 152阅读 0赞 **先摆模板。。。** **//线段树模板 struct line \{** **int left,right;//左端点、右端点 int n;//记录这条线段出现了多少次,默认为0 \}; struct line a\[100\]; int sum; //建立 void build(int s,int t,int n) \{** **int mid=(s+t)/2; a\[n\].left=s; a\[n\].right=t; if (s==t) return; a\[n\].left=s; a\[n\].right=t; build(s,mid,2\*n); build(mid+1,t,2\*n+1); \} //插入 void insert(int s,int t,int step)//要插入的线段的左端点和右端点、以及当前线段树中的某条线段 \{ if (s==a\[step\].left && t==a\[step\].right) \{ a\[step\].n++;//插入的线段匹配则此条线段的记录\+1 return;//插入结束返回 \} if (a\[step\].left==a\[step\].right) return;//当前线段树的线段没有儿子,插入结束返回 int mid=(a\[step\].left+a\[step\].right)/2; if (mid>=t) insert(s,t,step\*2);//如果中点在t的右边,则应该插入到左儿子 else if (mid<s) insert(s,t,step\*2+1);//如果中点在s的左边,则应该插入到右儿子 else//否则,中点一定在s和t之间,把待插线段分成两半分别插到左右儿子里面 \{ insert(s,mid,step\*2); insert(mid+1,t,step\*2+1); \} \} //访问 void count (int s,int t,int step) \{ ** ** if (a\[step\].n!=0)** **sum=sum+a\[step\].n\*(t-s+1); if (a\[step\].left==a\[step\].right)** **return; int mid=(a\[step\].left+a\[step\].right)/2; if (mid>=t)** **count(s,t,step\*2); else** ** if (mid<s)** ** count(s,t,step\*2+1); else \{ count(s,mid,step\*2); count(mid+1,t,step\*2+1); \} \}** **下面来自某大牛解释:** **线段树的定义** 定义1 长度为1的线段称为元线段。 定义2 一棵树被成为线段树,当且仅当这棵树满足如下条件: (1) 该树是一棵二叉树。 (2) 树中每一个结点都对应一条线段\[a,b\]。 (3) 树中结点是叶子结点当且仅当它所代表的线段是元线段。 (4) 树中非叶子结点都有左右两个子树,做子树树根对应线段\[a , (a + b ) / 2\],右子树树根对应线段\[( a + b ) / 2 , b\]。 但是这种二叉树较为平衡,和静态二叉树一样,提前根据应用的部分建立好树形结构。针对性强,所以效率要高。一般来说,动态结构较为灵活,但是速度较慢;静态结构节省内存,速度较快。 ** 线段树的性质与时空复杂度简介** 下面介绍线段树的两个性质(证明略)。 性质1 长度范围为\[1,L\]的一棵线段树的深度不超过log(L-1) + 1。 性质2 线段树把区间上的任意一条长度为L的线段都分成不超过2logL条线段。 空间复杂度 存储一棵线段树的空间复杂度一般为O(L)。 时间复杂度 对于插入线段、删除线段,查找元素,查找区间最值等操作,复杂度一般都是O(log L)。 线段树主要应用了平衡与分治的性质,所以基本时间复杂度都和log有关。我们在应用线段树解决问题的时候,应尽量在构造好线段树的时候,使每种操作在同一层面上操作的次数为O(1),这样能够维持整体的复杂度O(log L)。 例题: 在自然数,且所有的数不大于30000的范围内讨论一个问题:现在已知n条线段,把端点依次输入告诉你,然后有m个询问,每个询问输入一个点,要求这个点在多少条线段上出现过; 最基本的解法当然就是读一个点,就把所有线段比一下,看看在不在线段中; 每次询问都要把n条线段查一次,那么m次询问,就要运算m\*n次,复杂度就是O(m\*n) 这道题m和n都是30000,那么计算量达到了10^9;而计算机1秒的计算量大约是10^8的数量级,所以这种方法无论怎么优化都是超时 \----- 因为n条线段是固定的,所以某种程度上说每次都把n条线段查一遍有大量的重复和浪费; 线段树就是可以解决这类问题的数据结构 举例说明:已知线段\[2,5\] \[4,6\] \[0,7\];求点2,4,7分别出现了多少次 在\[0,7\]区间上建立一棵满二叉树:(为了和已知线段区别,用【】表示线段树中的线段) 【0,7】 / \\ 【0,3】 【4,7】 / \\ / \\ 【0,1】 【2,3】 【4,5】 【6,7】 / \\ / \\ / \\ / \\ 【0,0】【1,1】【2,2】 【3,3】【4,4】 【5,5】 【6,6】【7,7】 每个节点用结构体: struct line \{ int left,right;//左端点、右端点 int n;//记录这条线段出现了多少次,默认为0 \}a\[16\]; 和堆类似,满二叉树的性质决定a\[i\]的左儿子是a\[2\*i\]、右儿子是a\[2\*i+1\]; 然后对于已知的线段依次进行插入操作: 从树根开始调用递归函数insert void insert(int s,int t,int step)//要插入的线段的左端点和右端点、以及当前线段树中的某条线段 \{ if (s==a\[step\].left && t==a\[step\].right) \{ a\[step\].n++;//插入的线段匹配则此条线段的记录+1 return;//插入结束返回 \} if (a\[step\].left==a\[step\].right) return;//当前线段树的线段没有儿子,插入结束返回 int mid=(a\[step\].left+a\[step\].right)/2; if (mid>=t) insert(s,t,step\*2);//如果中点在t的右边,则应该插入到左儿子 else if (mid<s) insert(s,t,step\*2+1);//如果中点在s的左边,则应该插入到右儿子 else//否则,中点一定在s和t之间,把待插线段分成两半分别插到左右儿子里面 \{ insert(s,mid,step\*2); insert(mid+1,t,step\*2+1); \} \} 三条已知线段插入过程: \[2,5\] \--\[2,5\]与【0,7】比较,分成两部分:\[2,3\]插到左儿子【0,3】,\[4,5\]插到右儿子【4,7】 \--\[2,3\]与【0,3】比较,插到右儿子【2,3】;\[4,5\]和【4,7】比较,插到左儿子【4,5】 \--\[2,3\]与【2,3】匹配,【2,3】记录+1;\[4,5\]与【4,5】匹配,【4,5】记录+1 \[4,6\] \--\[4,6\]与【0,7】比较,插到右儿子【4,7】 \--\[4,6\]与【4,7】比较,分成两部分,\[4,5\]插到左儿子【4,5】;\[6,6\]插到右儿子【6,7】 \--\[4,5\]与【4,5】匹配,【4,5】记录+1;\[6,6\]与【6,7】比较,插到左儿子【6,6】 \--\[6,6\]与【6,6】匹配,【6,6】记录+1 \[0,7\] \--\[0,7\]与【0,7】匹配,【0,7】记录+1 插入过程结束,线段树上的记录如下(红色数字为每条线段的记录n): 【0,7】 1 / \\ 【0,3】 【4,7】 0 0 / \\ / \\ 【0,1】 【2,3】 【4,5】 【6,7】 0 1 2 0 / \\ / \\ / \\ / \\ 【0,0】 【1,1】 【2,2】 【3,3】 【4,4】 【5,5】 【6,6】 【7,7】 0 0 0 0 0 0 1 0 询问操作和插入操作类似,也是递归过程,略 2——依次把【0,7】 【0,3】 【2,3】【2,2】的记录n加起来,结果为2 4——依次把【0,7】 【4,7】 【4,5】【4,4】的记录n加起来,结果为3 7——依次把【0,7】 【4,7】 【6,7】【7,7】的记录n加起来,结果为1 不管是插入操作还是查询操作,每次操作的执行次数仅为树的深度——logN 建树有n次插入操作,n\*logN,一次查询要logN,m次就是m\*logN;总共复杂度O(n+m)\*logN,这道题N不超过30000,logN约等于14,所以计算量在10^5~10^6之间,比普通方法快了1000倍; 这道题是线段树最基本的操作,只用到了插入和查找;删除操作和插入类似,扩展功能的还有测度、连续段数等等,在N数据范围很大的时候,依然可以用离散化的方法建树
还没有评论,来说两句吧...