【数据结构】线段树(Segment Tree)
副标题[/!--empirenews.page--]
? 假设我们现在拿到了一个非常大的数组,对于这个数组里面的数字要反复不断地做两个操作。 1、(query)随机在这个数组中选一个区间,求出这个区间所有数的和。 2、(update)不断地随机修改这个数组中的某一个值。 时间复杂度: 枚举: 枚举L~R的每个数并累加。
找到要修改的数直接修改。
如果query与update要做很多很多次,query的O(n)会被卡住,所以时间复杂度会非常慢。那么有没有办法把query的时间复杂度降成O(1)呢?其中一种方法如下:
前缀和: query:O(1) update:O(n)
线段树假设我们拿到了如下长度为6的数组: 在构建线段树之前,我们先阐述线段树的性质: 1、线段树的每个节点都代表一个区间。 2、线段树具有唯一的根节点,代表的区间是整个统计范围,如[1,N]。 3、线段树的每个叶节点都代表一个长度为1的元区间[x,x]。 4、对于每个内部节点[l,r],它的左子结点是[l,mid],右子节点是[mid+1,r],其中mid=(l+r)/2(向下取整)。 依照这个数组,我们构建如下线段树(结点的性质为sum): 若我们要求[2-5]区间中数的和: 若我们要把a[4]改为6:
? ? 接下来的问题是:如何保存这棵线段树?
若我们要取node结点的左子结点(left)与右子节点(right),方法如下:
举结点5为例(左子结点为节点11,右子节点为节点12):
接下来给出建树的代码: (编辑:开发网_开封站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |