本文概述
让我们考虑一下下面的问题,以便在不使用递归的情况下理解线段树。
我们有一个数组arr[0…n - 1)。我们应该能够,
- 找出从索引l到r的元素总和, 其中0 <= l <= r <= n-1
- 将数组的指定元素的值更改为新值x。我们需要做arr [i] = x, 其中0 <= i <= n-1。
一种简单的解决方案是运行从l到r的循环, 并计算给定范围内的元素之和。要更新值, 只需做arr [i] = x。第一次手术需要上)时间和第二次手术需要O(1)时间。
另一种解决方案是创建另一个数组, 并将从开始到i的和存储在该数组的第i个索引处。现在可以以O(1)的时间计算给定范围的总和, 但是现在更新操作需要O(n)的时间。如果查询操作的数量很大且更新很少, 则此方法效果很好。
如果查询次数和更新次数相等怎么办?给定数组后, 是否可以在O(log n)时间内执行两项操作?我们可以使用线段树在O(Logn)时间内执行这两项操作。我们已经讨论了线段树的完整实现以前发布。在这篇文章中, 我们将讨论一种比上一篇文章更简单, 更有效的实现线段树的方法。
考虑如下所示的数组和线段树:
从上图可以看到, 原始数组位于底部, 并使用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 = 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 = 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 = 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 = 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.
输出如下:
5
3
与以前的递归代码相比, 用更少的代码行数完整地实现了包含查询和更新功能的线段树。现在让我们了解每个函数的工作方式:
- 图片清楚地表明叶节点存储在i + n处, 因此我们可以清楚地直接插入所有叶节点。
- 下一步是构建树, 这需要O(n)时间。父级的索引始终小于子级, 因此我们只按降序处理所有节点, 计算父级节点的值。如果构建函数中用于计算父级的代码令人困惑, 那么你可以看到此代码, 它等同于构建函数中的代码。
tree[i]=tree[2*i]+tree[2*i+1]
- 在任何位置更新值也很简单, 花费的时间将与树的高度成比例。我们仅更新要更改的给定节点的父节点中的值。因此, 为了获取父节点, 我们只需转到节点p的父节点p / 2或p >> 1。 p ^ 1将(2 * i)变成(2 * i + 1), 反之亦然, 得到p的第二个孩子。
- 计算总和也可以在O(log(n))时间中进行。如果我们以[3, 11)的间隔工作, 则仅需要按该顺序计算节点19、26、12和5。
查询功能背后的想法是, 我们应该在总和中包括元素还是应该包括其父元素。让我们再次看一下图像, 以便正确理解。考虑L是区间的左边界, R是区间[L, R)的右边界。从图片中可以清楚地看到, 如果L为奇数, 则表示它是其父级的正确子级, 并且我们的时间间隔仅包含L而不是其父级。因此, 我们将简单地包括该节点以求和并通过执行L =(L + 1)/ 2移至其下一个节点的父节点。现在, 如果L为偶数, 则它是其父级的左子级, 并且除非右边界干扰, 否则interval还将包括它的父级。类似的条件也适用于右边界, 以加快计算速度。一旦左右边界相遇, 我们将停止此迭代。
先前实现和此实现的理论时间复杂度相同, 但实际上, 由于没有递归调用, 因此效率更高。我们只是简单地迭代所需的元素。同样, 这很容易实现。
时间复杂度:
- 树构造:O(n)
- 查询范围:O(Log n)
- 更新元素:O(Log n)。
参考文献:
http://codeforces.com/blog/entry/18051
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。