下一个→ ←上一页

段树-给定范围的和

让我们考虑下面的问题来理解段树。

我们有一个数组arr[0…]n - 1)。我们应该能够做到

求从索引l到r中0 <= l <= r <= n-1的元素的和
将数组中指定元素的值更改为新值x．我们需要做arr[i] = x其中0 <= i <= n-1。

使用嵌套循环的Range sum:

运行一个从l到r的循环并计算所提供范围内元素的和是一个简单的解决方案。只需输入arr[i] = x即可更改值。第一个操作需要O(n)时间，而第二个操作只需要O(1)时间。

使用前缀和的范围总数:

另一种方法是创建一个新数组，并将从start到I的总数放在第I个索引处。更新过程现在需要O(n)时间，而给定范围的总数可以在O(1)时间内计算出来。如果有很多查询操作和很少的更新，这可以很好地工作。

使用段树的范围总数:

最有效的方法是利用段树;我们可以在O(log(N))时间内使用段树来完成这两个操作。

段树表示

输入数组中的元素是叶节点。
每个内部节点显示叶节点是如何以某种方式合并的。对于某些问题，可能会有不同的合并。总结一个节点下的叶节点就是这个问题的合并。
段树被显示为树的数组表示。每个节点在索引I处的左子节点是index (2* I +1)，右子节点是index (2* I +2)，父节点是index (I - 1) / 2)。

从提供的数组构建一个段树

我们首先检查段arr[0，…]n - 1)。每次，我们将当前段分成两半(假设它还没有成为长度为1的段)，在两半上运行相同的操作，然后将每个这样的段的结果存储在适当的节点中。

除了最后一层，创建的段树的每一层都将被完全填充。此外，由于我们总是在每一层将每个片段分成两个，因此该树将是一个完整的二叉树。总是有n-1个内部节点因为创建的树总是一个有n个叶子的完整二叉树。因此，总共会有2*n - 1个节点。

提供的数组的段树有多高?

段树的高度为log2N。分配给段树的内容量将是(2 * 2log2n-1)，因为树必须使用数组表示，并且必须保留父索引和子索引之间的关系。

搜索一个范围的和

如何计算的总和使用段树一旦它已经建立。计算元素和的算法如下。

            int getSum(node, l, r){如果节点的范围在l之内，r返回节点中的值;如果节点的范围完全在l之外，r返回0;否则返回getSum(节点的左子节点，l, r) + getSum(节点的右子节点，l, r)}
           

在上述实现中，我们需要解决三种情况。

在遍历树时，如果当前节点的取值范围不在指定范围内，则不将该节点的值添加到答案中。
如果提供的范围与节点的范围部分重叠，则根据重叠的范围向左或向右移动。
如果给定的范围与答案完全重叠，则将该范围添加到答案中。

更新值:

更新可以递归地执行，就像树构建和查询操作一样。提供给我们的是一个过时的索引。让diff表示新值。从段树的根开始，我们向每个在其范围内具有指定索引的节点追加diff。如果节点在其范围内没有指定的索引，则不修改节点。

c++代码

上述战略的应用情况如下:

            #include <bits/stdc++.h> using namespace std;//从角索引中获取中间索引的实用函数。int getMid(int s, int e){返回s + (e -s)/2;} /*一个递归函数，用于获取给定数组范围内的值和。以下是该函数的参数。st——>指向段树的指针si——>段树当前节点的索引。最初是作为根总是在传递指数0 ss和se - >开始和结束段由当前节点的索引,即圣(si) qs和量化宽松政策——>索引的查询范围的开始和结束* / int getSumUtil (int * st, int党卫军,int, int qs, int量化宽松,int si){/ /如果段节点给定范围的一部分,然后返回/ /段的总和如果(qs < =党卫军& & qe > = se)返回圣(si);//如果该节点的段在给定范围之外If (se < qs || ss > qe)返回0;//如果这个段的一部分与给定的范围重叠int mid = getMid(ss, se);返回getSumUtil(st, s, mid, qs, qe, 2*si+1) + getSumUtil(st, mid+1, se, qs, qe, 2*si+2); } /* A recursive function to update the nodes which have the given index in their range. The following are parameters st, si, ss and se are same as getSumUtil() i --> index of the element to be updated. This index is in the input array. diff --> Value to be added to all nodes which have i in range */ void updateValueUtil(int *st, int ss, int se, int i, int diff, int si) { // Base Case: If the input index lies outside the range of // this segment if (i < ss || i > se) return; // If the input index is in range of this node, then update // the value of the node and its children st[si] = st[si] + diff; if (se != ss) { int mid = getMid(ss, se); updateValueUtil(st, ss, mid, i, diff, 2*si + 1); updateValueUtil(st, mid+1, se, i, diff, 2*si + 2); } } // The function to update a value in input array and segment tree. // It uses updateValueUtil() to update the value in segment tree void updateValue(int arr[], int *st, int n, int i, int new_val) { // Check for erroneous input index if (i < 0 || i > n-1) { cout<<"Invalid Input"; return; } // Get the difference between new value and old value int diff = new_val - arr[i]; // Update the value in array arr[i] = new_val; // Update the values of nodes in segment tree updateValueUtil(st, 0, n-1, i, diff, 0); } // Return sum of elements in range from index qs (query start) // to qe (query end). It mainly uses getSumUtil() int getSum(int *st, int n, int qs, int qe) { // Check for erroneous input values if (qs < 0 || qe > n-1 || qs > qe) { cout<<"Invalid Input"; return -1; } return getSumUtil(st, 0, n-1, qs, qe, 0); } // A recursive function that constructs Segment Tree for array[ss..se]. // si is index of current node in segment tree st int constructSTUtil(int arr[], int ss, int se, int *st, int si) { // If there is one element in array, store it in current node of // segment tree and return if (ss == se) { st[si] = arr[ss]; return arr[ss]; } // If there are more than one elements, then recur for left and // right subtrees and store the sum of values in this node int mid = getMid(ss, se); st[si] = constructSTUtil(arr, ss, mid, st, si*2+1) + constructSTUtil(arr, mid+1, se, st, si*2+2); return st[si]; } /* Function to construct segment tree from given array. This function allocates memory for segment tree and calls constructSTUtil() to fill the allocated memory */ int *constructST(int arr[], int n) { // Allocate memory for the segment tree //Height of segment tree int x = (int)(ceil(log2(n))); //Maximum size of segment tree int max_size = 2*(int)pow(2, x) - 1; // Allocate memory int *st = new int[max_size]; // Fill the allocated memory st constructSTUtil(arr, 0, n-1, st, 0); // Return the constructed segment tree return st; } // Driver program to test above functions int main() { int arr[] = {1, 3, 5, 7, 9, 11}; int n = sizeof(arr)/sizeof(arr[0]); // Build segment tree from given array int *st = constructST(arr, n); // Print sum of values in array from index 1 to 3 cout<<"Sum of values in given range = "<<getSum(st, n, 1, 3)<<endl; // Update: set arr[1] = 10 and update corresponding // segment tree nodes updateValue(arr, st, n, 1, 10); // Find sum after the value is updated cout<<"Updated sum of values in given range = " <<getSum(st, n, 1, 3)<<endl; return 0; }
           

输出:

给定范围内的值之和= 15更新后的给定范围内的值之和= 22

时间复杂度:O (N * log (N))
辅助空间:O (N)

下一个话题 2-3树(查找、插入、删除)

←上一页下一个→

视频加入我们的Youtube频道:现在加入

反馈

将你的意见发送至(电子邮件保护)

帮助别人，请分享

学习最新教程

Splunk

SPSS

2022世界杯赛程安排

transact - sql

Tumblr

ReactJS

正则表达式

强化学习

世界杯2022赛程时间表最新

RxJS

反应本地

Python设计模式

Python的枕头

Python的乌龟

Keras

准备

资质

世界杯2022赛程时间表

语言能力

面试问题

公司的问题

b .技术/马华

2022世界杯预选赛

数据结构

DAA

操作系统

计算机网络

编译器设计

计算机组织

离散数学

道德黑客

计算机图形学

软件工程

网络技术

网络安全

自动机

C编程

c++

Java

net

Python

项目

控制系统

数据挖掘

数据仓库

2022世+D11837:D11850界杯八强让球

JavaTpoint提供了太多高质量的服务。邮件地址:(电子邮件保护)，以获取有关特定服务的更多信息。

网站设计
网站开发
世界杯欧洲杯小组赛
PHP开发
WordPress
平面设计
标志
2022卡塔尔世界杯赛程图
页面上和页面外的SEO
PPC
内容开发
企业培训
课堂和在线培训
数据输入

大学校园培训

JavaTpoint提供核心Java、高级Java、。net、Android、Hadoop、PHP、Web技术和Python的大学校园培训。请将您的要求寄至(电子邮件保护)
持续时间:1 - 2周

^{喜欢/订阅我们以获取最新更新或通讯}

DS教程

DS数组

DS链表

DS堆栈

DS队列

DS树

DS图

DS搜索

DS排序

差异

Misc

DS MCQ