使用二叉索引树计算右侧的较小元素和左侧的较大元素 _二叉索引树

本文概述

C ++
Java
Python3

给定大小为n的数组arr[]，任务是为给定数组中的每个元素arr[i]寻找右边较小的元素和左边较大的元素。
例子：

输入：arr [] = {12, 1, 2, 3, 0, 11, 4}输出：右较小：6 1 1 1 0 1 0左较大：0 1 1 1 4 1 2输入：arr [] = { 5, 4, 3, 2, 1}输出：右小：4 3 2 1 0左大：0 1 2 3 4输入：arr [] = {1, 2, 3, 4, 5}输出：右小： 0 0 0 0 0左上角：0 0 0 0 0

前提条件:使用BIT在数组中计数反转现
方法:我们已经在这篇文章中讨论了计算右边较小元素的实现。这里，我们将使用二叉索引树来计算数组中每个元素的右边较小的元素和左边较大的元素。
首先，从右到左遍历数组，并在右侧找到前面文章中建议的较小的元素。然后重置位数组，并从左到右遍历该数组，在左边找到更大的元素。
【使用二叉索引树计算右侧的较小元素和左侧的较大元素】下面是上述方法的实现：
C ++

// C++ implementation of the approach #include < bits/stdc++.h> using namespace std; // Function to return the sum of arr[0..index] // This function assumes that the array is preprocessed // and partial sums of array elements are stored in BITree[] int getSum( int BITree[], int index) { int sum = 0; // Initialize result// Traverse ancestors of BITree[index] while (index > 0) { // Add current element of BITree to sum sum += BITree[index]; // Move index to parent node in getSum View index -= index & (-index); } return sum; }// Updates a node in Binary Index Tree (BITree) at given index // in BITree. The given value 'val' is added to BITree[i] and // all of its ancestors in tree. void updateBIT( int BITree[], int n, int index, int val) { // Traverse all ancestors and add 'val' while (index < = n) {// Add 'val' to current node of BI Tree BITree[index] += val; // Update index to that of parent in update View index += index & (-index); } }// Converts an array to an array with values from 1 to n // and relative order of smaller and greater elements remains // same. For example, {7, -90, 100, 1} is converted to // {3, 1, 4, 2 } void convert( int arr[], int n) { // Create a copy of arrp[] in temp and sort the temp array // in increasing order int temp[n]; for ( int i = 0; i < n; i++) temp[i] = arr[i]; sort(temp, temp + n); // Traverse all array elements for ( int i = 0; i < n; i++) { // lower_bound() Returns pointer to the first element // greater than or equal to arr[i] arr[i] = lower_bound(temp, temp + n, arr[i]) - temp + 1; } }// Function to find smaller_right array void findElements( int arr[], int n) { // Convert arr[] to an array with values from 1 to n and // relative order of smaller and greater elements remains // same. For example, {7, -90, 100, 1} is converted to // {3, 1, 4, 2 } convert(arr, n); // Create a BIT with size equal to maxElement+1 (Extra // one is used so that elements can be directly be // used as index) int BIT[n + 1]; for ( int i = 1; i < = n; i++) BIT[i] = 0; // To store smaller elements in right side // and greater elements on left side int smaller_right[n], greater_left[n]; // Traverse all elements from right. for ( int i = n - 1; i > = 0; i--) {// Get count of elements smaller than arr[i] smaller_right[i] = getSum(BIT, arr[i] - 1); // Add current element to BIT updateBIT(BIT, n, arr[i], 1); }cout < < "Smaller right: " ; // Print smaller_right array for ( int i = 0; i < n; i++) cout < < smaller_right[i] < < " " ; cout < < endl; for ( int i = 1; i < = n; i++) BIT[i] = 0; // Find all left side greater elements for ( int i = 0; i < n; i++) {// Get count of elements greater than arr[i] greater_left[i] = i - getSum(BIT, arr[i]); // Add current element to BIT updateBIT(BIT, n, arr[i], 1); }cout < < "Greater left: " ; // Print greater_left array for ( int i = 0; i < n; i++) cout < < greater_left[i] < < " " ; }// Driver code int main() { int arr[] = { 12, 1, 2, 3, 0, 11, 4 }; int n = sizeof (arr) / sizeof (arr[0]); // Function call findElements(arr, n); return 0; }

Java

// Java implementation of the approach import java.io.*; import java.util.*; class GFG{// Function to return the sum of // arr[0..index]. This function // assumes that the array is // preprocessed and partial sums // of array elements are stored in BITree[] public static int getSum( int BITree[], int index) { // Initialize result int sum = 0 ; // Traverse ancestors of BITree[index] while (index > 0 ) {// Add current element of BITree to sum sum += BITree[index]; // Move index to parent node in getSum View index -= index & (-index); } return sum; } // Updates a node in Binary Index Tree // (BITree) at given index in BITree. // The given value 'val' is added to BITree[i] // and all of its ancestors in tree. public static void updateBIT( int BITree[], int n, int index, int val) { // Traverse all ancestors and add 'val' while (index < = n) { // Add 'val' to current node of BI Tree BITree[index] += val; // Update index to that of parent // in update View index += index & (-index); } } // Converts an array to an array with values // from 1 to n and relative order of smaller // and greater elements remains same. // For example, {7, -90, 100, 1} is converted to // {3, 1, 4, 2 } public static void convert( int arr[], int n) { // Create a copy of arrp[] in temp // and sort the temp array in // increasing order int [] temp = new int [n]; for ( int i = 0 ; i < n; i++) temp[i] = arr[i]; Arrays.sort(temp); // Traverse all array elements for ( int i = 0 ; i < n; i++) {// Arrays.binarySearch() returns index // to the first element greater than // or equal to arr[i] arr[i] = Arrays.binarySearch(temp, arr[i]) + 1 ; } } // Function to find smaller_right array public static void findElements( int arr[], int n) { // Convert arr[] to an array with values // from 1 to n and relative order of smaller // and greater elements remains same. For // example, {7, -90, 100, 1} is converted to // {3, 1, 4, 2 } convert(arr, n); // Create a BIT with size equal to // maxElement+1 (Extra one is used // so that elements can be directly be // used as index) int [] BIT = new int [n + 1 ]; for ( int i = 1 ; i < = n; i++) BIT[i] = 0 ; // To store smaller elements in right side // and greater elements on left side int [] smaller_right = new int [n]; int [] greater_left = new int [n]; // Traverse all elements from right. for ( int i = n - 1 ; i > = 0 ; i--) { // Get count of elements smaller than arr[i] smaller_right[i] = getSum(BIT, arr[i] - 1 ); // Add current element to BIT updateBIT(BIT, n, arr[i], 1 ); } System.out.print( "Smaller right: " ); // Print smaller_right array for ( int i = 0 ; i < n; i++) System.out.print(smaller_right[i] + " " ); System.out.println(); for ( int i = 1 ; i < = n; i++) BIT[i] = 0 ; // Find all left side greater elements for ( int i = 0 ; i < n; i++) { // Get count of elements greater than arr[i] greater_left[i] = i - getSum(BIT, arr[i]); // Add current element to BIT updateBIT(BIT, n, arr[i], 1 ); } System.out.print( "Greater left: " ); // Print greater_left array for ( int i = 0 ; i < n; i++) System.out.print(greater_left[i] + " " ); } // Driver code public static void main(String[] args) { int arr[] = { 12 , 1 , 2 , 3 , 0 , 11 , 4 }; int n = arr.length; // Function call findElements(arr, n); } }// This code is contributed by kunalsg18elec

Python3

# Python3 implementation of the approach from bisect import bisect_left as lower_bound# Function to return the sum of arr[0..index] # This function assumes that the array is # preprocessed and partial sums of array elements # are stored in BITree[] def getSum(BITree, index):# Initialize result s = 0# Traverse ancestors of BITree[index] while index > 0 :# Add current element of BITree to sum s + = BITree[index]# Move index to parent node in getSum View index - = index & ( - index)return s# Updates a node in Binary Index Tree (BITree) # at given index in BITree. The given value 'val' # is added to BITree[i] and all of its ancestors in tree. def updateBIT(BITree, n, index, val):# Traverse all ancestors and add 'val' while index < = n:# Add 'val' to current node of BI Tree BITree[index] + = val# Update index to that of parent in update View index + = index & ( - index)# Converts an array to an array with values # from 1 to n and relative order of smaller # and greater elements remains same. # For example, {7, -90, 100, 1} is # converted to {3, 1, 4, 2 } def convert(arr, n):# Create a copy of arrp[] in temp and # sort the temp array in increasing order temp = [ 0 ] * n for i in range (n): temp[i] = arr[i]temp.sort()# Traverse all array elements for i in range (n):# lower_bound() Returns pointer to the first element # greater than or equal to arr[i] arr[i] = lower_bound(temp, arr[i]) + 1# Function to find smaller_right array def findElements(arr, n):# Convert arr[] to an array with values # from 1 to n and relative order of smaller and # greater elements remains same. For example, # {7, -90, 100, 1} is converted to {3, 1, 4, 2 } convert(arr, n)# Create a BIT with size equal to maxElement+1 # (Extra one is used so that elements can be # directly be used as index) BIT = [ 0 ] * (n + 1 )# To store smaller elements in right side # and greater elements on left side smaller_right = [ 0 ] * n greater_left = [ 0 ] * n# Traverse all elements from right. for i in range (n - 1 , - 1 , - 1 ):# Get count of elements smaller than arr[i] smaller_right[i] = getSum(BIT, arr[i] - 1 )# Add current element to BIT updateBIT(BIT, n, arr[i], 1 )print ( "Smaller right:" , end = " " ) for i in range (n): print (smaller_right[i], end = " " ) print ()# Print smaller_right array for i in range ( 1 , n + 1 ): BIT[i] = 0# Find all left side greater elements for i in range (n):# Get count of elements greater than arr[i] greater_left[i] = i - getSum(BIT, arr[i])# Add current element to BIT updateBIT(BIT, n, arr[i], 1 )print ( "Greater left:" , end = " " )# Print greater_left array for i in range (n): print (greater_left[i], end = " " ) print ()# Driver Code if __name__ = = "__main__" :arr = [ 12 , 1 , 2 , 3 , 0 , 11 , 4 ] n = len (arr)# Function call findElements(arr, n)# This code is contributed by # sanjeev2552

输出如下：