Consultas de rango para contar elementos que se encuentran en un rango dado: Algoritmo de MO

Dada una array arr[] de N elementos y dos números enteros A a B , la tarea es responder Q consultas, cada una de las cuales tiene dos números enteros L y R. Para cada consulta, encuentre el número de elementos en el subarreglo arr[L…R] que se encuentra dentro del rango A a B (inclusive).

Ejemplos:

Entrada: arr[] = {7, 3, 9, 13, 5, 4}, A = 4, B = 7
consulta = {1, 5}
Salida: 2
Explicación:
Solo 5 y 4 se encuentran entre 4 y 7
en el subarreglo {3, 9, 13, 5, 4}
Por lo tanto, la cuenta de dichos elementos es 2.

Entrada: arr[] = {0, 1, 2, 3, 4, 5, 6, 7}, A = 1, B = 5 consulta =
{3, 5}
Salida: 3
Explicación:
Todos los elementos 3, 4 y 5 se encuentra dentro
del rango de 1 a 5 en el subarreglo {3, 4, 5}.
Por lo tanto, la cuenta de tales elementos es 3.

Prerrequisitos: Algoritmo de MO , Descomposición SQRT

Enfoque: la idea es usar el algoritmo de MO para preprocesar todas las consultas de modo que el resultado de una consulta se pueda usar en la siguiente consulta. A continuación se muestra la ilustración de los pasos:

• Agrupe las consultas en varios fragmentos donde cada fragmento contiene los valores del rango inicial en (0 a √N – 1), (√N a 2x√N – 1), y así sucesivamente. Ordene las consultas dentro de un fragmento en orden creciente de R .
• Procese todas las consultas una por una de manera que cada consulta use el resultado calculado en la consulta anterior.
• Mantenga la array de frecuencias que contará la frecuencia de arr[i] tal como aparecen en el rango [L, R].

Por ejemplo: arr[] = [3, 4, 6, 2, 7, 1], L = 0, R = 4 y A = 1, B = 6 Inicialmente, la array de frecuencia se inicializa en 0, es decir, freq[]=[
0 ….0]
Paso 1: agregue arr[0] e incremente su frecuencia como freq[arr[0]]++, es decir, freq[3]++
y freq[]=[0, 0, 0, 1, 0, 0 , 0, 0]
Paso 2: agregue arr[1] e incremente freq[arr[1]]++, es decir, freq[4]++
y freq[]=[0, 0, 0, 1, 1, 0, 0 , 0]
Paso 3: agregue arr[2] e incremente freq[arr[2]]++, es decir, freq[6]++
y freq[]=[0, 0, 0, 1, 1, 0, 1, 0 ]
Paso 4: agregue arr[3] e incremente freq[arr[3]]++, es decir, freq[2]++
y freq[]=[0, 0, 1, 1, 1, 0, 1, 0]
Paso 5: Agregue arr[4] e incremente freq[arr[4]]++, es decir, freq[7]++
and freq[]=[0, 0, 1, 1, 1, 0, 1, 1]
Paso 6: Ahora necesitamos encontrar el número de elementos entre A y B.
Paso 7: La respuesta es igual a 
Para calcular el sum en el paso 7, no podemos hacer la iteración porque eso conduciría a una complejidad de tiempo O(N) por consulta, por lo que usaremos la técnica de descomposición sqrt para encontrar la suma cuya complejidad de tiempo es O(√N) por consulta .
 

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

// C++ implementation to find the
// values in the range A to B
// in a subarray of L to R
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 100001
#define SQRSIZE 400
 
// Variable to represent block size.
// This is made global so compare()
// of sort can use it.
int query_blk_sz;
 
// Structure to represent a
// query range
struct Query {
    int L;
    int R;
};
 
// Frequency array
// to keep count of elements
int frequency[MAX];
 
// Array which contains the frequency
// of a particular block
int blocks[SQRSIZE];
 
// Block size
int blk_sz;
 
// Function used to sort all queries
// so that all queries of the same
// block are arranged together and
// within a block, queries are sorted
// in increasing order of R values.
bool compare(Query x, Query y)
{
    if (x.L / query_blk_sz != y.L / query_blk_sz)
        return x.L / query_blk_sz < y.L / query_blk_sz;
 
    return x.R < y.R;
}
 
// Function used to get the block
// number of current a[i] i.e ind
int getblocknumber(int ind)
{
    return (ind) / blk_sz;
}
 
// Function to get the answer
// of range [0, k] which uses the
// sqrt decomposition technique
int getans(int A, int B)
{
    int ans = 0;
    int left_blk, right_blk;
    left_blk = getblocknumber(A);
    right_blk = getblocknumber(B);
 
    // If left block is equal to
    // right block then we can traverse
    // that block
    if (left_blk == right_blk) {
        for (int i = A; i <= B; i++)
            ans += frequency[i];
    }
    else {
        // Traversing first block in
        // range
        for (int i = A; i < (left_blk + 1) * blk_sz; i++)
            ans += frequency[i];
 
        // Traversing completely overlapped
        // blocks in range
        for (int i = left_blk + 1;
            i < right_blk; i++)
            ans += blocks[i];
 
        // Traversing last block in range
        for (int i = right_blk * blk_sz;
            i <= B; i++)
            ans += frequency[i];
    }
    return ans;
}
 
void add(int ind, int a[])
{
    // Increment the frequency of a[ind]
    // in the frequency array
    frequency[a[ind]]++;
 
    // Get the block number of a[ind]
    // to update the result in blocks
    int block_num = getblocknumber(a[ind]);
 
    blocks[block_num]++;
}
void remove(int ind, int a[])
{
    // Decrement the frequency of
    // a[ind] in the frequency array
    frequency[a[ind]]--;
 
    // Get the block number of a[ind]
    // to update the result in blocks
    int block_num = getblocknumber(a[ind]);
 
    blocks[block_num]--;
}
void queryResults(int a[], int n,
                Query q[], int m, int A, int B)
{
 
    // Initialize the block size
    // for queries
    query_blk_sz = sqrt(m);
 
    // Sort all queries so that queries
    // of same blocks are arranged
    // together.
    sort(q, q + m, compare);
 
    // Initialize current L,
    // current R and current result
    int currL = 0, currR = 0;
 
    for (int i = 0; i < m; i++) {
 
        // L and R values of the
        // current range
 
        int L = q[i].L, R = q[i].R;
 
        // Add Elements of current
        // range
        while (currR <= R) {
            add(currR, a);
            currR++;
        }
        while (currL > L) {
            add(currL - 1, a);
            currL--;
        }
 
        // Remove element of previous
        // range
        while (currR > R + 1)
 
        {
            remove(currR - 1, a);
            currR--;
        }
        while (currL < L) {
            remove(currL, a);
            currL++;
        }
        printf("%d\n", getans(A, B));
    }
}
 
// Driver code
int main()
{
 
    int arr[] = { 2, 0, 3, 1, 4, 2, 5, 11 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    int A = 1, B = 5;
    blk_sz = sqrt(N);
    Query Q[] = { { 0, 2 }, { 0, 3 }, { 5, 7 } };
 
    int M = sizeof(Q) / sizeof(Q[0]);
 
    // Answer the queries
    queryResults(arr, N, Q, M, A, B);
    return 0;
}

// Java implementation to find the
// values in the range A to B
// in a subarray of L to R
import java.util.*;
import java.lang.Math;
 
public class GFG {
 
  public static int MAX=100001;
  public static int SQRSIZE=400;
 
  // Variable to represent block size.
  // This is made global so compare()
  // of sort can use it.
  public static int query_blk_sz;
 
  // Frequency array
  // to keep count of elements
  public static int[] frequency = new int[MAX];
 
  // Array which contains the frequency
  // of a particular block
  public static int[] blocks = new int[SQRSIZE];
 
  // Block size
  public static int blk_sz;
 
  // Function used to sort all queries
  // so that all queries of the same
  // block are arranged together and
  // within a block, queries are sorted
  // in increasing order of R values.
 
  static Comparator<int[]> arrayComparator = new Comparator<int[]>() {
    @Override
    public int compare(int[] x, int[] y) {
      if (x[0] / query_blk_sz != y[0] / query_blk_sz)
        return Integer.compare(x[0] / query_blk_sz, y[0] / query_blk_sz);
 
      return Integer.compare(x[1],y[1]);
    }
  };
 
  // Function used to get the block
  // number of current a[i] i.e ind
  public static int getblocknumber(int ind)
  {
    return (ind) / blk_sz;
  }
 
  // Function to get the answer
  // of range [0, k] which uses the
  // sqrt decomposition technique
  public static int getans(int A, int B)
  {
    int ans = 0;
    int left_blk, right_blk;
    left_blk = getblocknumber(A);
    right_blk = getblocknumber(B);
 
    // If left block is equal to
    // right block then we can traverse
    // that block
    if (left_blk == right_blk) {
      for (int i = A; i <= B; i++)
        ans += frequency[i];
    }
    else {
      // Traversing first block in
      // range
      for (int i = A; i < (left_blk + 1) * blk_sz; i++)
        ans += frequency[i];
 
      // Traversing completely overlapped
      // blocks in range
      for (int i = left_blk + 1;
           i < right_blk; i++)
        ans += blocks[i];
 
      // Traversing last block in range
      for (int i = right_blk * blk_sz;
           i <= B; i++)
        ans += frequency[i];
    }
    return ans;
  }
 
  public static void add(int ind, int a[])
  {
 
    // Increment the frequency of a[ind]
    // in the frequency array
    frequency[a[ind]]++;
 
    // Get the block number of a[ind]
    // to update the result in blocks
    int block_num = getblocknumber(a[ind]);
 
    blocks[block_num]++;
  }
  public static void remove(int ind, int a[])
  {
 
    // Decrement the frequency of
    // a[ind] in the frequency array
    frequency[a[ind]]--;
 
    // Get the block number of a[ind]
    // to update the result in blocks
    int block_num = getblocknumber(a[ind]);
 
    blocks[block_num]--;
  }
  public static void queryResults(int a[], int n,
                                  int[][] q, int m, int A, int B)
  {
 
    // Initialize the block size
    // for queries
    query_blk_sz = (int)Math.sqrt(m);
 
    // Sort all queries so that queries
    // of same blocks are arranged
    // together.
    Arrays.sort(q,arrayComparator);
 
    // Initialize current L,
    // current R and current result
    int currL = 0, currR = 0;
 
    for (int i = 0; i < m; i++) {
 
      // L and R values of the
      // current range
 
      int L = q[i][0], R = q[i][1];
 
      // Add Elements of current
      // range
      while (currR <= R) {
        add(currR, a);
        currR++;
      }
      while (currL > L) {
        add(currL - 1, a);
        currL--;
      }
 
      // Remove element of previous
      // range
      while (currR > R + 1)
 
      {
        remove(currR - 1, a);
        currR--;
      }
      while (currL < L) {
        remove(currL, a);
        currL++;
      }
      System.out.println(getans(A, B));
    }
  }
 
  // Driver code
  public static void main(String[] args) {
    int arr[] = { 2, 0, 3, 1, 4, 2, 5, 11 };
    int N = arr.length;
 
    int A = 1, B = 5;
    blk_sz = (int) Math.sqrt(N);
    int[][] Q = { { 0, 2 }, { 0, 3 }, { 5, 7 } };
 
    int M = Q.length;
 
    // Answer the queries
    queryResults(arr, N, Q, M, A, B);
  }
}
 
// This code is contributed
// by Shubham Singh

# Python implementation to find the
# values in the range A to B
# in a subarray of L to R
import math
from functools import cmp_to_key
MAX = 100001
SQRSIZE = 400
 
# Variable to represent block size.
# This is made global so compare()
# of sort can use it.
query_blk_sz = 1
 
# Frequency array
# to keep count of elements
frequency = [0] * MAX
 
# Array which contains the frequency
# of a particular block
blocks = [0]*SQRSIZE
 
# Block size
blk_sz = 0
 
# Function used to sort all queries
# so that all queries of the same
# block are arranged together and
# within a block, queries are sorted
# in increasing order of R values.
 
 
def compare(x, y):
    if ((x[0] // query_blk_sz) != (y[0] // query_blk_sz)):
        return x[0] // query_blk_sz < y[0] // query_blk_sz
 
    return x[1] < y[1]
 
 
# Function used to get the block
# number of current a[i] i.e ind
def getblocknumber(ind):
    return (ind) // blk_sz
 
# Function to get the answer
# of range [0, k] which uses the
# sqrt decomposition technique
 
 
def getans(A, B):
    ans = 0
 
    left_blk = getblocknumber(A)
    right_blk = getblocknumber(B)
 
    # If left block is equal to
    # right block then we can traverse
    # that block
    if (left_blk == right_blk):
        for i in range(A, B+1):
            ans += frequency[i]
 
    else:
        # Traversing first block in
        # range
        i = A
        while(i < (left_blk+1)*blk_sz):
            ans += frequency[i]
            i += 1
 
        # Traversing completely overlapped
        # blocks in range
        i = (int)(left_blk + 1)
        while(i < right_blk):
            ans += blocks[i]
            i += 1
 
        # Traversing last block in range
        i = (int)(right_blk * blk_sz)
        while(i <= B):
            ans += frequency[i]
            i += 1
 
    return ans
 
 
def add(ind, a):
 
    # Increment the frequency of a[ind]
    # in the frequency array
    frequency[a[ind]] += 1
 
    # Get the block number of a[ind]
    # to update the result in blocks
    block_num = getblocknumber(a[ind])
 
    blocks[(int)(block_num)] += 1
 
 
def remove(ind, a):
 
    # Decrement the frequency of
    # a[ind] in the frequency array
    frequency[a[ind]] -= 1
 
    # Get the block number of a[ind]
    # to update the result in blocks
    block_num = getblocknumber(a[ind])
 
    blocks[(int)(block_num)] -= 1
 
 
def queryResults(a, n, q, m, A, B):
 
    # Initialize the block size
    # for queries
    query_blk_sz = (int)(math.sqrt(m))
 
    # Sort all queries so that queries
    # of same blocks are arranged
    # together.
    q.sort(key=cmp_to_key(compare))
 
    # Initialize current L,
    # current R and current result
    currL = 0
    currR = 0
 
    for i in range(0, m):
 
        # L and R values of the
        # current range
 
        L = q[i][0]
        R = q[i][1]
 
        # Add Elements of current
        # range
        while (currR <= R):
            add(currR, a)
            currR += 1
 
        while (currL > L):
            add(currL - 1, a)
            currL -= 1
 
        # Remove element of previous
        # range
        while (currR > R + 1):
            remove(currR - 1, a)
            currR -= 1
 
        while (currL < L):
            remove(currL, a)
            currL += 1
 
        print(getans(A, B))
 
 
# Driver code
arr = [2, 0, 3, 1, 4, 2, 5, 11]
N = len(arr)
 
A = 1
B = 5
blk_sz = (int)(math.sqrt(N))
 
Q = [[0, 2], [0, 3], [5, 7]]
 
M = len(Q)
 
# Answer the queries
queryResults(arr, N, Q, M, A, B)
 
# This code is contributed by rj113to.

2
3
2