Dada una array de enteros arr , la tarea es contar el número de inversiones en la array.
Si A[i] > A[j] e i < j entonces el par (A[i], A[j]) es parte de una inversión.
Ejemplos:
Entrada: arr[] = {8, 4, 2, 1}
Salida: 6
Entrada: arr[] = {3, 1, 2}
Salida: 2
Acercarse:
- Cree un árbol de segmentos en el que cada Node represente los números totales presentes en el rango de ese Node.
- Digamos que el rango de cualquier Node es [i, j], entonces el Node contendrá el recuento de números que son mayores o iguales que i y menores o iguales que j.
- Los Nodes de hoja solo serán 1 o 0, ya que el rango del Node será 1.
- Itere a través de la array, deje que el número presente en el índice i sea a[i]. Encontraremos cuántos números están presentes en el árbol de segmentos en el rango [a[i]+1, max] donde max es el elemento máximo de la array y lo agregaremos a la variable de respuesta.
- Luego insertaremos ese número en el árbol de segmentos y continuaremos hasta el último índice de la array. De esta manera, para cada elemento, estamos sumando los números que aparecen antes de ese elemento y son mayores que ese elemento, es decir, forman un par de inversión.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count the inversions
// present in the array using segment tree
#include "algorithm"
#include "cstring"
#include "iostream"
using namespace std;
// Function to update segment tree
// i.e. to insert the element
void update(int* Tree, int index, int s, int e, int num)
{
// Leaf node condition
if (s == num and e == num) {
Tree[index] = 1;
return;
}
// No overlap condition
if (num < s or num > e) {
return;
}
// Else call on both the children nodes
int mid = (s + e) >> 1;
update(Tree, 2 * index, s, mid, num);
update(Tree, 2 * index + 1, mid + 1, e, num);
Tree[index] = Tree[2 * index] + Tree[2 * index + 1];
}
// Function to count the total numbers
// present in the range [a[i]+1, mx]
int query(int* Tree, int index, int s,
int e, int qs, int qe)
{
// Complete overlap
if (qs <= s and e <= qe) {
return Tree[index];
}
// No Overlap
if (s > qe or e < qs) {
return 0;
}
int mid = (s + e) >> 1;
return query(Tree, 2 * index, s,
mid, qs, qe)
+ query(Tree, 2 * index + 1,
mid + 1, e, qs, qe);
}
// Driver code
int main(int argc, char const* argv[])
{
int arr[] = { 8, 4, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
// Maximum element present in the array.
int mx = *max_element(arr, arr + n);
// Segment Tree
int Tree[6 * mx];
// Initialize every node
// of segment tree to 0
memset(Tree, 0, sizeof(Tree));
int answer = 0;
for (int i = 0; i < n; ++i) {
// add the count of inversion pair
// formed with the element a[i] and the
// elements appearing before the index i.
answer += query(Tree, 1, 1, mx, arr[i] + 1, mx);
// Insert the a[i] in the segment tree
update(Tree, 1, 1, mx, arr[i]);
}
cout << answer;
return 0;
}
Java
// Java program to count the inversions
// present in the array using segment tree
import java.io.*;
import java.util.Arrays;
class GFG
{
// Function to update segment tree
// i.e. to insert the element
static void update(int[] Tree, int index,
int s, int e, int num)
{
// Leaf node condition
if (s == num && e == num)
{
Tree[index] = 1;
return;
}
// No overlap condition
if (num < s || num > e)
{
return;
}
// Else call on both the children nodes
int mid = (s + e) >> 1;
update(Tree, 2 * index, s, mid, num);
update(Tree, 2 * index + 1, mid + 1, e, num);
Tree[index] = Tree[2 * index] + Tree[2 * index + 1];
}
// Function to count the total numbers
// present in the range [a[i]+1, mx]
static int query(int[] Tree, int index, int s,
int e, int qs, int qe)
{
// Complete overlap
if (qs <= s && e <= qe)
{
return Tree[index];
}
// No Overlap
if (s > qe || e < qs)
{
return 0;
}
int mid = (s + e) >> 1;
return query(Tree, 2 * index, s, mid, qs, qe) +
query(Tree, 2 * index + 1, mid + 1, e, qs, qe);
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 8, 4, 2, 1 };
int n = arr.length;
// Maximum element present in the array.
int mx = Arrays.stream(arr).max().getAsInt();
// Segment Tree
int[] Tree = new int[6 * mx];
int answer = 0;
for (int i = 0; i < n; ++i)
{
// add the count of inversion pair
// formed with the element a[i] and the
// elements appearing before the index i.
answer += query(Tree, 1, 1, mx, arr[i] + 1, mx);
// Insert the a[i] in the segment tree
update(Tree, 1, 1, mx, arr[i]);
}
System.out.println(answer);
}
}
// This code is contributed by rag2127
Python3
# Python3 program to count the inversions # present in the array using segment tree # Function to update segment tree # i.e. to insert the element def update(Tree, index, s, e, num): # Leaf node condition if (s == num and e == num): Tree[index] = 1 return # No overlap condition if (num < s or num > e): return # Else call on both the children nodes mid = (s + e) >> 1 update(Tree, 2 * index, s, mid, num) update(Tree, 2 * index + 1, mid + 1, e, num) Tree[index] = Tree[2 * index] + Tree[2 * index + 1] # Function to count the total numbers # present in the range [a[i]+1, mx] def query(Tree,index, s,e, qs, qe): # Complete overlap if (qs <= s and e <= qe): return Tree[index] # No Overlap if (s > qe or e < qs): return 0 mid = (s + e) >> 1 return query(Tree, 2 * index, s,mid, qs, qe) +\ query(Tree, 2 * index + 1, mid + 1, e, qs, qe) # Driver code if __name__ == '__main__': arr = [8, 4, 2, 1] n = len(arr) # Maximum element present in the array. mx = max(arr) # Segment Tree Tree = [0] * (6 * mx) # Initialize every node # of segment tree to 0 answer = 0 for i in range(n): # add the count of inversion pair # formed with the element a[i] and the # elements appearing before the index i. answer += query(Tree, 1, 1, mx, arr[i] + 1, mx) # Insert the a[i] in the segment tree update(Tree, 1, 1, mx, arr[i]) print(answer) # This code is contributed by Mohit Kumar
C#
using System;
using System.Linq;
class GFG
{
// Function to update segment tree
// i.e. to insert the element
static void update(int[] Tree, int index,
int s, int e, int num)
{
// Leaf node condition
if (s == num && e == num)
{
Tree[index] = 1;
return;
}
// No overlap condition
if (num < s || num > e)
{
return;
}
// Else call on both the children nodes
int mid = (s + e) >> 1;
update(Tree, 2 * index, s, mid, num);
update(Tree, 2 * index + 1, mid + 1, e, num);
Tree[index] = Tree[2 * index] + Tree[2 * index + 1];
}
// Function to count the total numbers
// present in the range [a[i]+1, mx]
static int query(int[] Tree, int index,
int s, int e, int qs, int qe)
{
// Complete overlap
if (qs <= s && e <= qe)
{
return Tree[index];
}
// No Overlap
if (s > qe || e < qs)
{
return 0;
}
int mid = (s + e) >> 1;
return query(Tree, 2 * index, s, mid, qs, qe) +
query(Tree, 2 * index + 1, mid + 1, e, qs, qe);
}
// Driver code
static public void Main ()
{
int[] arr = { 8, 4, 2, 1 };
int n = arr.Length;
// Maximum element present in the array.
int mx = arr.Max();
// Segment Tree
int[] Tree = new int[6 * mx];
int answer = 0;
for (int i = 0; i < n; ++i)
{
// add the count of inversion pair
// formed with the element a[i] and the
// elements appearing before the index i.
answer += query(Tree, 1, 1, mx, arr[i] + 1, mx);
// Insert the a[i] in the segment tree
update(Tree, 1, 1, mx, arr[i]);
}
Console.WriteLine(answer);
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// JavaScript program to count the inversions
// present in the array using segment tree
// Function to update segment tree
// i.e. to insert the element
function update(Tree,index,s,e,num)
{
// Leaf node condition
if (s == num && e == num)
{
Tree[index] = 1;
return;
}
// No overlap condition
if (num < s || num > e)
{
return;
}
// Else call on both the children nodes
let mid = (s + e) >> 1;
update(Tree, 2 * index, s, mid, num);
update(Tree, 2 * index + 1, mid + 1, e, num);
Tree[index] = Tree[2 * index] + Tree[2 * index + 1];
}
// Function to count the total numbers
// present in the range [a[i]+1, mx]
function query(Tree, index, s,
e, qs, qe)
{
// Complete overlap
if (qs <= s && e <= qe)
{
return Tree[index];
}
// No Overlap
if (s > qe || e < qs)
{
return 0;
}
let mid = (s + e) >> 1;
return query(Tree, 2 * index, s, mid, qs, qe) +
query(Tree, 2 * index + 1, mid + 1, e, qs, qe);
}
// Driver code
let arr=[ 8, 4, 2, 1 ];
let n = arr.length;
// Maximum element present in the array.
let mx = Math.max(...arr);
// Segment Tree
let Tree = new Array(6 * mx);
for(let i=0;i<Tree.length;i++)
{
Tree[i]=0;
}
let answer = 0;
for (let i = 0; i < n; ++i)
{
// add the count of inversion pair
// formed with the element a[i] and the
// elements appearing before the index i.
answer += query(Tree, 1, 1, mx, arr[i] + 1, mx);
// Insert the a[i] in the segment tree
update(Tree, 1, 1, mx, arr[i]);
}
document.write(answer);
// This code is contributed by unknown2108
</script>
Producción:
6
Publicación traducida automáticamente
Artículo escrito por imdhruvgupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA