Número de elementos mayores que K en el rango L a R utilizando Fenwick Tree (consultas sin conexión)

Prerrequisitos: Fenwick Tree (Árbol indexado binario)
Dada una array de N números y una cantidad de consultas donde cada consulta contendrá tres números (l, r y k). La tarea es calcular el número de elementos del arreglo que son mayores que K en el subarreglo [L, R]. 
Ejemplos: 
 

Input:  n=6                                           
         q=2                                           
         arr[ ] = { 7, 3, 9, 13, 5, 4 }  
         Query1: l=1, r=4, k=6
         Query2: l=2, r=6, k=8

Output: 3
         2

For the first query, [7, 3, 9, 13] represents the 
subarray from index 1 till 4, in which there are 
3 numbers which are greater than k=6 that are {7, 9, 13}.

For the second query, there are only 
two numbers in the query range which
are greater than k.

El enfoque ingenuo es encontrar la respuesta para cada consulta simplemente recorriendo la array desde el índice l hasta r y seguir agregando 1 al conteo siempre que el elemento de la array sea mayor que k. 
Complejidad de tiempo: O(n*q)
Un mejor enfoque es utilizar el árbol de ordenación por fusión. En este enfoque, construya un árbol de segmentos con un vector en cada Node que contenga todos los elementos del subrango en un orden ordenado. Responda cada consulta usando el árbol de segmentos donde se puede usar la búsqueda binaria para calcular cuántos números están presentes en cada Node cuyo subrango se encuentra dentro del rango de consulta que son mayores que k. 
Complejidad del tiempo: O(q * log(n) * log(n))
Un enfoque eficiente es resolver el problema usando consultas fuera de línea yÁrboles Fenwick. A continuación se muestran los pasos: 
 

• Primero almacene todos los elementos de la array y las consultas en la misma array. Para ello, podemos crear una estructura propia o clase.
• Luego, ordene la array estructural en orden descendente (en caso de colisión, la consulta aparecerá primero y luego el elemento de la array).
• Procese toda la array de estructura nuevamente, pero antes de eso, cree otra array BIT (Árbol indexado binario) cuya función de consulta (i) devolverá el recuento de todos los elementos que están presentes en la array hasta el i-ésimo índice.
• Inicialmente, llene toda la array con 0.
• Cree una array de respuestas, en la que se almacenan las respuestas de cada consulta.
• Procese la array de estructura.
• Si es un elemento de array, actualice la array BIT con +1 del índice de ese elemento.
• Si es una consulta, reste la consulta (r) – consulta (l-1) y esta será la respuesta para esa consulta que se almacenará en la array de respuesta en el índice correspondiente al número de consulta.
• Finalmente, genere la array de respuesta.

La observación clave aquí es que, dado que la array de la estructura se ha ordenado en orden descendente. Cada vez que encontramos una consulta, solo los elementos que son mayores que ‘k’ comprenden el recuento en la array BIT, que es la respuesta que se necesita. 
A continuación se muestra la explicación de la estructura utilizada en el programa: 
 

Pos: almacena el orden de consulta. En el caso de elementos de array se mantiene como 0. 
L: almacena el índice inicial del subarreglo de la consulta. En el caso de elementos de array también es 0. 
R: almacena el índice final del subarreglo de la consulta. En el caso de un elemento de array, se utiliza para almacenar la posición del elemento en la array. 
Val: almacena ‘k’ de la consulta y todos los elementos de la array. 
 

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to print the number of elements
// greater than k in a subarray of range L-R.
#include <bits/stdc++.h>
using namespace std;
 
// Structure which will store both
// array elements and queries.
struct node {
    int pos;
    int l;
    int r;
    int val;
};
 
// Boolean comparator that will be used
// for sorting the structural array.
bool comp(node a, node b)
{
    // If 2 values are equal the query will
    // occur first then array element
    if (a.val == b.val)
        return a.l > b.l;
 
    // Otherwise sorted in descending order.
    return a.val > b.val;
}
 
// Updates the node of BIT array by adding
// 1 to it and its ancestors.
void update(int* BIT, int n, int idx)
{
    while (idx <= n) {
        BIT[idx]++;
        idx += idx & (-idx);
    }
}
// Returns the count of numbers of elements
// present from starting till idx.
int query(int* BIT, int idx)
{
    int ans = 0;
    while (idx) {
        ans += BIT[idx];
 
        idx -= idx & (-idx);
    }
    return ans;
}
 
// Function to solve the queries offline
void solveQuery(int arr[], int n, int QueryL[],
                int QueryR[], int QueryK[], int q)
{
    // create node to store the elements
    // and the queries
    node a[n + q + 1];
    // 1-based indexing.
 
    // traverse for all array numbers
    for (int i = 1; i <= n; ++i) {
        a[i].val = arr[i - 1];
        a[i].pos = 0;
        a[i].l = 0;
        a[i].r = i;
    }
 
    // iterate for all queries
    for (int i = n + 1; i <= n + q; ++i) {
        a[i].pos = i - n;
        a[i].val = QueryK[i - n - 1];
        a[i].l = QueryL[i - n - 1];
        a[i].r = QueryR[i - n - 1];
    }
 
    // In-built sort function used to
    // sort node array using comp function.
    sort(a + 1, a + n + q + 1, comp);
 
    // Binary Indexed tree with
    // initially 0 at all places.
    int BIT[n + 1];
 
    // initially 0
    memset(BIT, 0, sizeof(BIT));
 
    // For storing answers for each query( 1-based indexing ).
    int ans[q + 1];
 
    // traverse for numbers and query
    for (int i = 1; i <= n + q; ++i) {
        if (a[i].pos != 0) {
 
            // call function to returns answer for each query
            int cnt = query(BIT, a[i].r) - query(BIT, a[i].l - 1);
 
            // This will ensure that answer of each query
            // are stored in order it was initially asked.
            ans[a[i].pos] = cnt;
        }
        else {
            // a[i].r contains the position of the
            // element in the original array.
            update(BIT, n, a[i].r);
        }
    }
    // Output the answer array
    for (int i = 1; i <= q; ++i) {
        cout << ans[i] << endl;
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 7, 3, 9, 13, 5, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // 1-based indexing
    int QueryL[] = { 1, 2 };
    int QueryR[] = { 4, 6 };
 
    // k for each query
    int QueryK[] = { 6, 8 };
 
    // number of queries
    int q = sizeof(QueryL) / sizeof(QueryL[0]);
 
    // Function call to get
    solveQuery(arr, n, QueryL, QueryR, QueryK, q);
 
    return 0;
}

# Python program to print the number of elements
# greater than k in a subarray of range L-R.
 
# Structure which will store both
# array elements and queries.
class node:
    def __init__(self):
        self.pos = 0
        self.l = 0
        self.r = 0
        self.val = 0
 
# Updates the node of BIT array by adding
# 1 to it and its ancestors.
def update(BIT: list, n: int, idx: int):
    while idx <= n:
        BIT[idx] += 1
        idx += idx & -idx
 
# Returns the count of numbers of elements
# present from starting till idx.
def query(BIT: list, idx: int) -> int:
    ans = 0
    while idx:
        ans += BIT[idx]
        idx -= idx & -idx
    return ans
 
# Function to solve the queries offline
def solveQuery(arr: list, n: int, QueryL: list,
                QueryR: list, QueryK: list, q: int):
 
    # create node to store the elements
    # and the queries
    a = [0] * (n + q + 1)
    for i in range(n + q + 1):
        a[i] = node()
     
    # 1-based indexing
 
    # traverse for all array numbers
    for i in range(1, n + 1):
        a[i].val = arr[i - 1]
        a[i].pos = 0
        a[i].l = 0
        a[i].r = i
 
    # iterate for all queries
    for i in range(n + 1, n + q + 1):
        a[i].pos = i - n
        a[i].val = QueryK[i - n - 1]
        a[i].l = QueryL[i - n - 1]
        a[i].r = QueryR[i - n - 1]
 
    # In-built sorted function used to
    # sort node array using comp function.
    a = [a[0]] + sorted(a[1:],
        key = lambda k: (k.val, k.l),
        reverse = True)
 
    # Binary Indexed tree with
    # initially 0 at all places.
    BIT = [0] * (n + 1)
 
    # For storing answers for
    # each query( 1-based indexing ).
    ans = [0] * (q + 1)
 
    # traverse for numbers and query
    for i in range(1, n + q + 1):
        if a[i].pos != 0:
 
            # call function to returns answer for each query
            cnt = query(BIT, a[i].r) - query(BIT, a[i].l - 1)
 
            # This will ensure that answer of each query
            # are stored in order it was initially asked.
            ans[a[i].pos] = cnt
        else:
 
            # a[i].r contains the position of the
            # element in the original array.
            update(BIT, n, a[i].r)
 
    # Output the answer array
    for i in range(1, q + 1):
        print(ans[i])
 
# Driver Code
if __name__ == "__main__":
 
    arr = [7, 3, 9, 13, 5, 4]
    n = len(arr)
 
    # 1-based indexing
    QueryL = [1, 2]
    QueryR = [4, 6]
 
    # k for each query
    QueryK = [6, 8]
 
    # number of queries
    q = len(QueryL)
 
    # Function call to get
    solveQuery(arr, n, QueryL, QueryR, QueryK, q)
 
# This code is contributed by
# sanjeev2552

3
2

Complejidad de tiempo: O(N * log N) donde N = (n+q)
¿Qué es una consulta fuera de línea?  
En algunas preguntas, es difícil responder consultas en cualquier orden aleatorio. Entonces, en lugar de responder cada consulta por separado, almacene todas las consultas y luego ordénelas en consecuencia para calcular la respuesta de manera eficiente. Almacene todas las respuestas y luego envíelas en el orden en que se dieron inicialmente. 
Esta técnica se llama Consulta fuera de línea .
Nota: En lugar de Fenwick Tree, también se puede usar el árbol de segmentos donde cada Node del árbol de segmentos almacenará la cantidad de elementos insertados hasta esa iteración. Las funciones de actualización y consulta cambiarán, el resto de la implementación seguirá siendo la misma.
Condición necesaria para la consulta fuera de línea:Esta técnica se puede usar solo cuando la respuesta de una consulta no depende de las respuestas de consultas anteriores, ya que después de clasificar, el orden de las consultas puede cambiar.