加入收藏 | 设为首页 | 会员中心 | 我要投稿 开发网_开封站长网 (http://www.0378zz.com/)- 科技、AI行业应用、媒体智能、低代码、办公协同!
当前位置: 首页 > 服务器 > 安全 > 正文

【数据结构】线段树(Segment Tree)

发布时间:2021-04-02 12:31:36 所属栏目:安全 来源:网络整理
导读:副标题#e# ? 假设我们现在拿到了一个非常大的数组,对于这个数组里面的数字要反复不断地做两个操作。 1、(query)随机在这个数组中选一个区间,求出这个区间所有数的和。 2、(update)不断地随机修改这个数组中的某一个值。 时间复杂度: 枚举: 枚举L~R
副标题[/!--empirenews.page--]

?

假设我们现在拿到了一个非常大的数组,对于这个数组里面的数字要反复不断地做两个操作。

【数据结构】线段树(Segment Tree)

1、(query)随机在这个数组中选一个区间,求出这个区间所有数的和。

【数据结构】线段树(Segment Tree)

2、(update)不断地随机修改这个数组中的某一个值。

【数据结构】线段树(Segment Tree)

时间复杂度:

【数据结构】线段树(Segment Tree)

枚举:

枚举L~R的每个数并累加。

  • query:O(n)

找到要修改的数直接修改。

  • update:O(1)

如果query与update要做很多很多次,query的O(n)会被卡住,所以时间复杂度会非常慢。那么有没有办法把query的时间复杂度降成O(1)呢?其中一种方法如下:

  • 先建立一个与a数组一样大的数组。

【数据结构】线段树(Segment Tree)

  • s[1]=a[1];s[2]=a[1]+a[2];s[3]=a[1]+a[2]+a[3];...;s[n]=a[1]+a[2]+a[3]+...+a[n](在s数组中存入a的前缀和)

【数据结构】线段树(Segment Tree)

  • 此时a[L]+a[L+1]+...+a[R]=s[R]-s[L-1],query的时间复杂度降为O(1)。
  • 但若要修改a[k]的值,随之也需修改s[k],s[k+1],...,s[n]的值,时间复杂度升为O(n)。

前缀和:

query:O(1)

update:O(n)

  • 我们发现,当我们想尽方法把其中一个操作的时间复杂度改成O(1)后,另一个操作的时间复杂度就会变为O(n)。当query与update的操作特别多时,不论用哪种方法,总体的时间复杂度都不会特别快。
  • 所以,我们将要讨论一种叫线段树的数据结构,它可以把这两个操作的时间复杂度平均一下,使得query和update的时间复杂度都落在O(n?log?n)上,从而增加整个算法的效率。

线段树

假设我们拿到了如下长度为6的数组:

【数据结构】线段树(Segment Tree)

在构建线段树之前,我们先阐述线段树的性质:

1、线段树的每个节点都代表一个区间。

2、线段树具有唯一的根节点,代表的区间是整个统计范围,如[1,N]。

3、线段树的每个叶节点都代表一个长度为1的元区间[x,x]。

4、对于每个内部节点[l,r],它的左子结点是[l,mid],右子节点是[mid+1,r],其中mid=(l+r)/2(向下取整)。

依照这个数组,我们构建如下线段树(结点的性质为sum):

【数据结构】线段树(Segment Tree)

若我们要求[2-5]区间中数的和:

【数据结构】线段树(Segment Tree)

若我们要把a[4]改为6:

  • 先一层一层找到目标节点修改,在依次向上修改当前节点的父节点。

?

?

【数据结构】线段树(Segment Tree)

接下来的问题是:如何保存这棵线段树?

  • 用数组存储。

【数据结构】线段树(Segment Tree)

若我们要取node结点的左子结点(left)与右子节点(right),方法如下:

  • left=2*node+1
  • right=2*ndoe+2

举结点5为例(左子结点为节点11,右子节点为节点12):

  • left5=2*5+1=11
  • right5=2*5+2=12

接下来给出建树的代码:

(编辑:开发网_开封站长网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

热点阅读