Ordene el árbol estadístico usando el árbol fenwick (BIT)

Dada una array de enteros con rango limitado (0 a 1000000). Necesitamos implementar un árbol de estadísticas de pedidos usando el árbol fenwick. 
Debe soportar cuatro operaciones: Insertar, Eliminar, Seleccionar y Clasificar. Aquí n denota el tamaño del árbol de Fenwick y q denota el número de consultas. 

Cada consulta debe ser una de las siguientes 4 operaciones. 

• insertElement(x) – Inserta el elemento x en el árbol de Fenwick, con O(log n) complejidad de tiempo en el peor de los casos
• deleteElement(x) – Elimina el elemento x del árbol de fenwick, con O(log n) complejidad de tiempo en el peor de los casos
• findKthSmallest(k) – Encuentra el k-ésimo elemento más pequeño almacenado en el árbol, con O(log n * log n) complejidad de tiempo en el peor de los casos
• findRank(x) – Encuentra el rango del elemento x en el árbol, es decir, su índice en la lista ordenada de elementos del árbol, con complejidad de tiempo O(log n)

Prerrequisito: Árbol Indexado Binario o Árbol Fenwick
La idea es crear un BIT de tamaño con límite máximo. Insertamos un elemento en BIT usándolo como índice. Cuando insertamos un elemento x, incrementamos los valores de todos los ancestros de x en 1. Para eliminar un elemento, disminuimos los valores de los ancestros en 1. Básicamente llamamos a la función estándar update() de BIT tanto para insertar como para eliminar. Para encontrar el rango, simplemente llamamos a la función estándar sum() de BIT. Para encontrar el k-ésimo elemento más pequeño, hacemos una búsqueda binaria en BIT.

// C++ program to find rank of an element
// and k-th smallest element.
#include <bits/stdc++.h>
using namespace std;
 
const int MAX_VAL = 1000001;
 
/* Updates element at index 'i' of BIT. */
void update(int i, int add, vector<int>& BIT)
{
    while (i > 0 && i < BIT.size())
    {
        BIT[i] += add;
        i = i + (i & (-i));
    }
}
 
/* Returns cumulative sum of all elements of
   fenwick tree/BIT from start upto and
   including element at index 'i'. */
int sum(int i, vector<int>& BIT)
{
    int ans = 0;
    while (i > 0)
    {
        ans += BIT[i];
        i = i - (i & (-i));
    }
 
    return ans;
}
 
// Returns lower bound for k in BIT.
int findKthSmallest(int k, vector<int> &BIT)
{
    // Do binary search in BIT[] for given
    // value k.
    int l = 0;
    int h = BIT.size();
    while (l < h)
    {
        int mid = (l + h) / 2;
        if (k <= sum(mid, BIT))
            h = mid;
        else
            l = mid+1;
    }
 
    return l;
}
 
// Insert x into BIT. We basically increment
// rank of all elements greater than x.
void insertElement(int x, vector<int> &BIT)
{
    update(x, 1, BIT);
}
 
// Delete x from BIT. We basically decreases
// rank of all elements greater than x.
void deleteElement(int x, vector<int> &BIT)
{
    update(x, -1, BIT);
}
 
// Returns rank of element. We basically
// return sum of elements from start to
// index x.
int findRank(int x, vector<int> &BIT)
{
    return sum(x, BIT);
}
 
// Driver code
int main()
{
    vector<int> BIT(MAX_VAL);
    insertElement(20, BIT);
    insertElement(50, BIT);
    insertElement(30, BIT);
    insertElement(40, BIT);
 
    cout << "2nd Smallest element is "
     << findKthSmallest(2, BIT) << endl;
 
    cout << "Rank of 40 is "
         << findRank(40, BIT) << endl;
 
    deleteElement(40, BIT);
 
    cout << "Rank of 50 is "
         << findRank(50, BIT) << endl;
 
    return 0;
}

// Java program to find rank of an element
// and k-th smallest element.
import java.util.Arrays;
 
class GFG{
 
static int MAX_VAL = 1000001;
 
// Updates element at index 'i' of BIT
static void update(int i, int add,
                   Integer[] BIT)
{
    while (i > 0 && i < BIT.length)
    {
        BIT[i] += add;
        i = i + (i & (-i));
    }
}
 
// Returns cumulative sum of all elements
// of fenwick tree/BIT from start upto
// and including element at index 'i'.
static int sum(int i, Integer[] BIT)
{
    int ans = 0;
    while (i > 0)
    {
        ans += BIT[i];
        i = i - (i & (-i));
    }
    return ans;
}
 
// Returns lower bound for k in BIT.
static int findKthSmallest(int k,
                           Integer[] BIT)
{
     
    // Do binary search in BIT[]
    // for given value k.
    int l = 0;
    int h = BIT.length;
     
    while (l < h)
    {
        int mid = (l + h) / 2;
        if (k <= sum(mid, BIT))
            h = mid;
        else
            l = mid + 1;
    }
    return l;
}
 
// Insert x into BIT. We basically
// increment rank of all elements
// greater than x.
static void insertElement(int x, Integer[] BIT)
{
    update(x, 1, BIT);
}
 
// Delete x from BIT. We basically
// decreases rank of all elements
// greater than x.
static void deleteElement(int x, Integer[] BIT)
{
    update(x, -1, BIT);
}
 
// Returns rank of element. We basically
// return sum of elements from start to
// index x.
static int findRank(int x, Integer[] BIT)
{
    return sum(x, BIT);
}
 
// Driver code
public static void main(String[] args)
{
    Integer[] BIT = new Integer[MAX_VAL];
      Arrays.fill(BIT, 0);
       
    insertElement(20, BIT);
    insertElement(50, BIT);
    insertElement(30, BIT);
    insertElement(40, BIT);
 
    System.out.println("2nd Smallest element is " +
                        findKthSmallest(2, BIT));
    System.out.println("Rank of 40 is " +
                        findRank(40, BIT));
 
    deleteElement(40, BIT);
     
    System.out.println("Rank of 50 is " +
                        findRank(50, BIT));
}
}
 
// This code is contributed by sanjeev2552

Producción: 

2nd Smallest element is 30
Rank of 40 is 3
Rank of 50 is 3

Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.