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

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

本文概述

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

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

# 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。

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

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