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

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

本文概述

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

我们有一个数组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: