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

本文概述

• 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

输出如下：

Smaller right: 6 1 1 1 0 1 0 
Greater left: 0 1 1 1 4 1 2

---