数据结构和算法:线段树(区间树)的高效实现方案介绍

2021年3月26日15:56:39 发表评论 1,363 次浏览

本文概述

让我们考虑一下下面的问题,以便在不使用递归的情况下理解线段树

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

  1. 找出从索引l到r的元素总和, 其中0 <= l <= r <= n-1
  2. 将数组的指定元素的值更改为新值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

与以前的递归代码相比, 用更少的代码行数完整地实现了包含查询和更新功能的线段树。现在让我们了解每个函数的工作方式:

  1. 图片清楚地表明叶节点存储在i + n处, 因此我们可以清楚地直接插入所有叶节点。
  2. 下一步是构建树, 这需要O(n)时间。父级的索引始终小于子级, 因此我们只按降序处理所有节点, 计算父级节点的值。如果构建函数中用于计算父级的代码令人困惑, 那么你可以看到此代码, 它等同于构建函数中的代码。
    tree[i]=tree[2*i]+tree[2*i+1]
    
  3. 在任何位置更新值也很简单, 花费的时间将与树的高度成比例。我们仅更新要更改的给定节点的父节点中的值。因此, 为了获取父节点, 我们只需转到节点p的父节点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为偶数, 则它是其父级的左子级, 并且除非右边界干扰, 否则interval还将包括它的父级。类似的条件也适用于右边界, 以加快计算速度。一旦左右边界相遇, 我们将停止此迭代。

先前实现和此实现的理论时间复杂度相同, 但实际上, 由于没有递归调用, 因此效率更高。我们只是简单地迭代所需的元素。同样, 这很容易实现。

时间复杂度:

  • 树构造:O(n)
  • 查询范围:O(Log n)
  • 更新元素:O(Log n)。

参考文献:

http://codeforces.com/blog/entry/18051

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: