让我们考虑下面的问题来理解没有递归的片段树。 我们有一个数组arr[0…n-1]。我们应该能够，
- 求从索引l到r的元素之和，其中0<=l<=r<=n-1
- 将数组中指定元素的值更改为新值x。我们需要执行arr[i]=x，其中0<=i<=n-1。
A. 简单解决方案 就是从l到r运行一个循环，并计算给定范围内的元素之和。要更新一个值，只需执行arr[i]=x。第一个操作需要 O（n） 时间和第二次手术需要 O（1） 时间
另一个解决方案 就是创建另一个数组，并在该数组的第i个索引处存储从start到i的总和。给定范围的总和现在可以在O（1）时间内计算，但更新操作现在需要O（n）时间。如果查询操作的数量很大，并且更新很少，那么这种方法很有效。 如果查询和更新的数量相等怎么办？一旦给定数组，我们能在O（logn）时间内执行这两个操作吗？我们可以使用 分段树 在O（Logn）时间内完成这两个操作。我们已经讨论了在我们的 以前的 邮递在这篇文章中，我们将讨论比前一篇文章更容易、更有效地实现分段树。 考虑数组和分段树，如下所示：
![图片[1]-段树|高效实现-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_excl.png)
从上图中可以看到，原始数组位于底部，由16个元素组成0索引。该树总共包含31个节点，其中叶节点或原始数组的元素从节点16开始。因此，我们可以使用一个2*N大小的数组轻松地为这个数组构建一个段树，其中N是原始数组中的元素数。叶节点将从该数组中的索引N开始，并上升到索引（2*N–1）。因此，原始数组中索引i处的元素将位于段树数组中的索引（i+N）处。现在要计算双亲，我们将从指数（N–1）开始向上移动。对于索引i，左子级将位于（2*i），右子级将位于（2*i+1）索引。因此，（2*i）和（2*i+1）节点上的值在第i个节点上组合，以构建树。 如上图所示，我们可以在这个树中以[L，R]为间隔进行查询，包括左索引（L），排除右索引（R）。 我们将使用位运算符实现所有这些乘法和加法运算。 让我们来看看完整的实现：
C++
#include <bits/stdc++.h> using namespace std; // limit for array size const int N = 100000; int n; // array size // Max size of tree int tree[2 * N]; // function to build the tree void build( int arr[]) { // insert leaf nodes in tree for ( int i=0; i<n; i++) tree[n+i] = arr[i]; // build the tree by calculating parents for ( int i = n - 1; i > 0; --i) tree[i] = tree[i<<1] + tree[i<<1 | 1]; } // function to update a tree node void updateTreeNode( int p, int value) { // set value at position p tree[p+n] = value; p = p+n; // move upward and update parents for ( int i=p; i > 1; i >>= 1) tree[i>>1] = tree[i] + tree[i^1]; } // function to get sum on interval [l, r) int query( int l, int r) { int res = 0; // loop to find the sum in the range for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l&1) res += tree[l++]; if (r&1) res += tree[--r]; } return res; } // driver program to test the above function int main() { int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; // n is global n = sizeof (a)/ sizeof (a[0]); // build tree build(a); // print the sum in range(1,2) index-based cout << query(1, 3)<<endl; // modify element at 2nd index updateTreeNode(2, 1); // print the sum in range(1,2) index-based cout << query(1, 3)<<endl; return 0; } |
JAVA
import java.io.*; public class GFG { // limit for array size static int N = 100000 ; static int n; // array size // Max size of tree static int []tree = new int [ 2 * N]; // function to build the tree static void build( int []arr) { // insert leaf nodes in tree for ( int i = 0 ; i < n; i++) tree[n + i] = arr[i]; // build the tree by calculating // parents for ( int i = n - 1 ; i > 0 ; --i) tree[i] = tree[i << 1 ] + tree[i << 1 | 1 ]; } // function to update a tree node static void updateTreeNode( int p, int value) { // set value at position p tree[p + n] = value; p = p + n; // move upward and update parents for ( int i = p; i > 1 ; i >>= 1 ) tree[i >> 1 ] = tree[i] + tree[i^ 1 ]; } // function to get sum on // interval [l, r) static int query( int l, int r) { int res = 0 ; // loop to find the sum in the range for (l += n, r += n; l < r; l >>= 1 , r >>= 1 ) { if ((l & 1 ) > 0 ) res += tree[l++]; if ((r & 1 ) > 0 ) res += tree[--r]; } return res; } // driver program to test the // above function static public void main (String[] args) { int []a = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 }; // n is global n = a.length; // build tree build(a); // print the sum in range(1,2) // index-based System.out.println(query( 1 , 3 )); // modify element at 2nd index updateTreeNode( 2 , 1 ); // print the sum in range(1,2) // index-based System.out.println(query( 1 , 3 )); } } // This code is contributed by vt_m. |
Python3
# Python3 Code Addition # limit for array size N = 100000 ; # Max size of tree tree = [ 0 ] * ( 2 * N); # function to build the tree def build(arr) : # insert leaf nodes in tree for i in range (n) : tree[n + i] = arr[i]; # build the tree by calculating parents for i in range (n - 1 , 0 , - 1 ) : tree[i] = tree[i << 1 ] + tree[i << 1 | 1 ]; # function to update a tree node def updateTreeNode(p, value) : # set value at position p tree[p + n] = value; p = p + n; # move upward and update parents i = p; while i > 1 : tree[i >> 1 ] = tree[i] + tree[i ^ 1 ]; i >> = 1 ; # function to get sum on interval [l, r) def query(l, r) : res = 0 ; # loop to find the sum in the range l + = n; r + = n; while l < r : if (l & 1 ) : res + = tree[l]; l + = 1 if (r & 1 ) : r - = 1 ; res + = tree[r]; l >> = 1 ; r >> = 1 return res; # Driver Code if __name__ = = "__main__" : a = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 ]; # n is global n = len (a); # build tree build(a); # print the sum in range(1,2) index-based print (query( 1 , 3 )); # modify element at 2nd index updateTreeNode( 2 , 1 ); # print the sum in range(1,2) index-based print (query( 1 , 3 )); # This code is contributed by AnkitRai01 |
C#
using System; public class GFG { // limit for array size static int N = 100000; static int n; // array size // Max size of tree static int []tree = new int [2 * N]; // function to build the tree static void build( int []arr) { // insert leaf nodes in tree for ( int i = 0; i < n; i++) tree[n + i] = arr[i]; // build the tree by calculating // parents for ( int i = n - 1; i > 0; --i) tree[i] = tree[i << 1] + tree[i << 1 | 1]; } // function to update a tree node static void updateTreeNode( int p, int value) { // set value at position p tree[p + n] = value; p = p + n; // move upward and update parents for ( int i = p; i > 1; i >>= 1) tree[i >> 1] = tree[i] + tree[i^1]; } // function to get sum on // interval [l, r) static int query( int l, int r) { int res = 0; // loop to find the sum in the range for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if ((l & 1) > 0) res += tree[l++]; if ((r & 1) > 0) res += tree[--r]; } return res; } // driver program to test the // above function static public void Main () { int []a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; // n is global n = a.Length; // build tree build(a); // print the sum in range(1,2) // index-based Console.WriteLine(query(1, 3)); // modify element at 2nd index updateTreeNode(2, 1); // print the sum in range(1,2) // index-based Console.WriteLine(query(1, 3)); } } // This code is contributed by vt_m. |
Javascript
<script> // limit for array size let N = 100000; let n; // array size // Max size of tree let tree = new Array(2 * N); tree.fill(0); // function to build the tree function build(arr) { // insert leaf nodes in tree for (let i = 0; i < n; i++) tree[n + i] = arr[i]; // build the tree by calculating // parents for (let i = n - 1; i > 0; --i) tree[i] = tree[i << 1] + tree[i << 1 | 1]; } // function to update a tree node function updateTreeNode(p, value) { // set value at position p tree[p + n] = value; p = p + n; // move upward and update parents for (let i = p; i > 1; i >>= 1) tree[i >> 1] = tree[i] + tree[i^1]; } // function to get sum on // interval [l, r) function query(l, r) { let res = 0; // loop to find the sum in the range for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if ((l & 1) > 0) res += tree[l++]; if ((r & 1) > 0) res += tree[--r]; } return res; } let a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]; // n is global n = a.length; // build tree build(a); // print the sum in range(1,2) // index-based document.write(query(1, 3) + "</br>" ); // modify element at 2nd index updateTreeNode(2, 1); // print the sum in range(1,2) // index-based document.write(query(1, 3)); </script> |
输出：
53
对仅此而已。段树的完整实现包括查询和更新功能，其代码行数低于之前的递归代码行数。现在让我们来了解每个功能是如何工作的：
1.图中明确表示叶节点存储在i+n，因此我们可以清楚地直接插入所有叶节点。
2.下一步是构建树，需要O（n）个时间。父节点的索引总是比子节点少，所以我们只需按降序处理所有节点，计算父节点的值。如果build函数中用于计算父对象的代码看起来令人困惑，那么您可以看到以下代码。它相当于build函数中的函数。
tree[i]=tree[2*i]+tree[2*i+1]
3.在任何位置更新值也很简单，所需时间将与树的高度成正比。我们只更新正在更改的给定节点的父节点中的值。为了得到父节点，我们只需转到父节点，即p/2或p>>1，节点p^1将（2*i）变成（2*i+1），反之亦然，得到p的第二个子节点。
4.计算总和也可以在O（log（n））时间内工作。如果我们计算[3,11]的时间间隔，我们只需要按照这个顺序计算节点19,26,12和5。
查询函数背后的想法是，我们是应该在求和中包含一个元素，还是应该包含它的父元素。让我们再看一次图片，以便正确理解。考虑到L是区间的左边界，R是区间[L，R ]的右边界。从图像中可以清楚地看出，如果L是奇数，则意味着它是其父的正确子集，并且我们的区间仅包含L而不是父。因此，我们将简单地将这个节点包括和通过L＝（L+1）移动到下一个节点的父节点。/2.现在，如果L是偶数，那么它是其父对象的左子对象，除非右边界干涉，否则区间也包括其父对象。类似的条件也适用于右边界，以加快计算速度。一旦左右边界相交，我们将停止此迭代。 以前的实现和这个实现在理论上的时间复杂度是相同的，但实际上，由于没有递归调用，它的效率要高得多。我们只需迭代所需的元素。而且，这很容易实现。
时间复杂性：
- 树木构造：O（n）
- 范围内的查询：O（日志n）
- 正在更新一个元素：O（logn）。
本文由 奋斗者 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
