Dada una array ‘a[]’ y un número de consultas q habrá dos tipos de consultas
- Actualización de consulta 0 (i, v): dos números enteros i y v, lo que significa establecer a [i] = v
- Consulta 1 cuenta (l, r, k): Necesitamos imprimir el número de enteros menores que iguales a k en el subarreglo l a r.
Dado a[i], v <= 10000 Ejemplos:
Input : arr[] = {5, 1, 2, 3, 4}
q = 6
1 1 3 1 // First value 1 means type of query is count()
0 3 10 // First value 0 means type of query is update()
1 3 3 4
0 2 1
0 0 2
1 0 4 5
Output :
1
0
4
For first query number of values less than equal to 1 in
arr[1..3] is 1(1 only), update a[3] = 10
There is no value less than equal to 4 in the a[3..3]
and similarly other queries are answered
Hemos discutido una solución que maneja solo consultas de recuento() en la publicación a continuación. Número de elementos menores o iguales a un número dado en un subarreglo dado Aquí también se debe manejar la consulta update(). Enfoque ingenuo El enfoque ingenuo es siempre que haya una operación de actualización, actualice la array y siempre que haya una consulta de tipo 2, atraviese el subarreglo y cuente los elementos válidos. Enfoque eficiente La idea es utilizar la descomposición de la raíz cuadrada
- Paso 1: divida la array en bloques de igual tamaño sqrt (n). Para cada bloque, mantenga un árbol de índice binario de tamaño igual a 1 más que el elemento máximo posible en la array de elementos de ese bloque.
- Paso 2: para cada elemento de la array, busque el bloque al que pertenece y actualice la array de bits de ese bloque con el valor 1 en arr[i].
- Paso 3: siempre que haya una consulta de actualización, actualice la array de bits del bloque correspondiente en el valor original de la array en ese índice con valor igual a -1 y actualice la array de bits del mismo bloque con valor 1 en el nuevo valor de la array en ese índice.
- Paso 4: para la consulta de tipo 2, puede realizar una sola consulta al BIT (para contar elementos menores o iguales a k) para cada bloque completo en el rango, y para los dos bloques parciales al final, simplemente recorra los elementos .
C++
// Number of elements less than or equal to a given
// number in a given subarray and allowing update
// operations.
#include<bits/stdc++.h>
using namespace std;
const int MAX = 10001;
// updating the bit array of a valid block
void update(int idx, int blk, int val, int bit[][MAX])
{
for (; idx<MAX; idx += (idx&-idx))
bit[blk][idx] += val;
}
// answering the query
int query(int l, int r, int k, int arr[], int blk_sz,
int bit[][MAX])
{
// traversing the first block in range
int sum = 0;
while (l<r && l%blk_sz!=0 && l!=0)
{
if (arr[l] <= k)
sum++;
l++;
}
// Traversing completely overlapped blocks in
// range for such blocks bit array of that block
// is queried
while (l + blk_sz <= r)
{
int idx = k;
for (; idx > 0 ; idx -= idx&-idx)
sum += bit[l/blk_sz][idx];
l += blk_sz;
}
// Traversing the last block
while (l <= r)
{
if (arr[l] <= k)
sum++;
l++;
}
return sum;
}
// Preprocessing the array
void preprocess(int arr[], int blk_sz, int n, int bit[][MAX])
{
for (int i=0; i<n; i++)
update(arr[i], i/blk_sz, 1, bit);
}
void preprocessUpdate(int i, int v, int blk_sz,
int arr[], int bit[][MAX])
{
// updating the bit array at the original
// and new value of array
update(arr[i], i/blk_sz, -1, bit);
update(v, i/blk_sz, 1, bit);
arr[i] = v;
}
// driver function
int main()
{
int arr[] = {5, 1, 2, 3, 4};
int n = sizeof(arr)/sizeof(arr[0]);
// size of block size will be equal to square root of n
int blk_sz = sqrt(n);
// initialising bit array of each block
// as elements of array cannot exceed 10^4 so size
// of bit array is accordingly
int bit[blk_sz+1][MAX];
memset(bit, 0, sizeof(bit));
preprocess(arr, blk_sz, n, bit);
cout << query (1, 3, 1, arr, blk_sz, bit) << endl;
preprocessUpdate(3, 10, blk_sz, arr, bit);
cout << query(3, 3, 4, arr, blk_sz, bit) << endl;
preprocessUpdate(2, 1, blk_sz, arr, bit);
preprocessUpdate(0, 2, blk_sz, arr, bit);
cout << query (0, 4, 5, arr, blk_sz, bit) << endl;
return 0;
}
Java
// Number of elements less than or equal to a given
// number in a given subarray and allowing update
// operations.
class Test
{
static final int MAX = 10001;
// updating the bit array of a valid block
static void update(int idx, int blk, int val, int bit[][])
{
for (; idx<MAX; idx += (idx&-idx))
bit[blk][idx] += val;
}
// answering the query
static int query(int l, int r, int k, int arr[], int blk_sz,
int bit[][])
{
// traversing the first block in range
int sum = 0;
while (l<r && l%blk_sz!=0 && l!=0)
{
if (arr[l] <= k)
sum++;
l++;
}
// Traversing completely overlapped blocks in
// range for such blocks bit array of that block
// is queried
while (l + blk_sz <= r)
{
int idx = k;
for (; idx > 0 ; idx -= idx&-idx)
sum += bit[l/blk_sz][idx];
l += blk_sz;
}
// Traversing the last block
while (l <= r)
{
if (arr[l] <= k)
sum++;
l++;
}
return sum;
}
// Preprocessing the array
static void preprocess(int arr[], int blk_sz, int n, int bit[][])
{
for (int i=0; i<n; i++)
update(arr[i], i/blk_sz, 1, bit);
}
static void preprocessUpdate(int i, int v, int blk_sz,
int arr[], int bit[][])
{
// updating the bit array at the original
// and new value of array
update(arr[i], i/blk_sz, -1, bit);
update(v, i/blk_sz, 1, bit);
arr[i] = v;
}
// Driver method
public static void main(String args[])
{
int arr[] = {5, 1, 2, 3, 4};
// size of block size will be equal to square root of n
int blk_sz = (int) Math.sqrt(arr.length);
// initialising bit array of each block
// as elements of array cannot exceed 10^4 so size
// of bit array is accordingly
int bit[][] = new int[blk_sz+1][MAX];
preprocess(arr, blk_sz, arr.length, bit);
System.out.println(query(1, 3, 1, arr, blk_sz, bit));
preprocessUpdate(3, 10, blk_sz, arr, bit);
System.out.println(query(3, 3, 4, arr, blk_sz, bit));
preprocessUpdate(2, 1, blk_sz, arr, bit);
preprocessUpdate(0, 2, blk_sz, arr, bit);
System.out.println(query (0, 4, 5, arr, blk_sz, bit));
}
}
Python3
# Number of elements less than or equal to a given # number in a given subarray and allowing update # operations. MAX = 10001 # updating the bit array of a valid block def update(idx, blk, val, bit): while idx < MAX: bit[blk][idx] += val idx += (idx & -idx) # answering the query def query(l, r, k, arr, blk_sz, bit): # traversing the first block in range summ = 0 while l < r and l % blk_sz != 0 and l != 0: if arr[l] <= k: summ += 1 l += 1 # Traversing completely overlapped blocks in # range for such blocks bit array of that block # is queried while l + blk_sz <= r: idx = k while idx > 0: summ += bit[l // blk_sz][idx] idx -= (idx & -idx) l += blk_sz # Traversing the last block while l <= r: if arr[l] <= k: summ += 1 l += 1 return summ # Preprocessing the array def preprocess(arr, blk_sz, n, bit): for i in range(n): update(arr[i], i // blk_sz, 1, bit) def preprocessUpdate(i, v, blk_sz, arr, bit): # updating the bit array at the original # and new value of array update(arr[i], i // blk_sz, -1, bit) update(v, i // blk_sz, 1, bit) arr[i] = v # Driver Code if __name__ == "__main__": arr = [5, 1, 2, 3, 4] n = len(arr) # size of block size will be equal # to square root of n from math import sqrt blk_sz = int(sqrt(n)) # initialising bit array of each block # as elements of array cannot exceed 10^4 # so size of bit array is accordingly bit = [[0 for i in range(MAX)] for j in range(blk_sz + 1)] preprocess(arr, blk_sz, n, bit) print(query(1, 3, 1, arr, blk_sz, bit)) preprocessUpdate(3, 10, blk_sz, arr, bit) print(query(3, 3, 4, arr, blk_sz, bit)) preprocessUpdate(2, 1, blk_sz, arr, bit) preprocessUpdate(0, 2, blk_sz, arr, bit) print(query(0, 4, 5, arr, blk_sz, bit)) # This code is contributed by # sanjeev2552
C#
// Number of elements less than or equal
// to a given number in a given subarray
// and allowing update operations.
using System;
class GFG
{
static int MAX = 10001;
// updating the bit array of a valid block
static void update(int idx, int blk,
int val, int [,]bit)
{
for (; idx < MAX; idx += (idx&-idx))
bit[blk, idx] += val;
}
// answering the query
static int query(int l, int r, int k, int []arr,
int blk_sz, int [,]bit)
{
// traversing the first block in range
int sum = 0;
while (l < r && l % blk_sz != 0 && l != 0)
{
if (arr[l] <= k)
sum++;
l++;
}
// Traversing completely overlapped blocks in
// range for such blocks bit array of that block
// is queried
while (l + blk_sz <= r)
{
int idx = k;
for (; idx > 0 ; idx -= idx&-idx)
sum += bit[l/blk_sz,idx];
l += blk_sz;
}
// Traversing the last block
while (l <= r)
{
if (arr[l] <= k)
sum++;
l++;
}
return sum;
}
// Preprocessing the array
static void preprocess(int []arr, int blk_sz,
int n, int [,]bit)
{
for (int i=0; i<n; i++)
update(arr[i], i / blk_sz, 1, bit);
}
static void preprocessUpdate(int i, int v, int blk_sz,
int []arr, int [,]bit)
{
// updating the bit array at the original
// and new value of array
update(arr[i], i/blk_sz, -1, bit);
update(v, i/blk_sz, 1, bit);
arr[i] = v;
}
// Driver method
public static void Main()
{
int []arr = {5, 1, 2, 3, 4};
// size of block size will be
// equal to square root of n
int blk_sz = (int) Math.Sqrt(arr.Length);
// initialising bit array of each block
// as elements of array cannot exceed 10^4 so size
// of bit array is accordingly
int [,]bit = new int[blk_sz+1,MAX];
preprocess(arr, blk_sz, arr.Length, bit);
Console.WriteLine(query(1, 3, 1, arr, blk_sz, bit));
preprocessUpdate(3, 10, blk_sz, arr, bit);
Console.WriteLine(query(3, 3, 4, arr, blk_sz, bit));
preprocessUpdate(2, 1, blk_sz, arr, bit);
preprocessUpdate(0, 2, blk_sz, arr, bit);
Console.WriteLine(query (0, 4, 5, arr, blk_sz, bit));
}
}
// This code is contributed by Sam007
Javascript
<script>
// Number of elements less than or equal to a given
// number in a given subarray and allowing update
// operations.
const MAX = 10001;
// updating the bit array of a valid block
function update(idx, blk, val, bit)
{
while(idx<MAX)
{
bit[blk][idx] += val;
idx += (idx&-idx);
}
}
// answering the query
function query(l, r, k, arr, blk_sz, bit)
{
// traversing the first block in range
var sum = 0;
while (l<r && l%blk_sz!=0 && l!=0)
{
if (arr[l] <= k)
sum++;
l++;
}
// Traversing completely overlapped blocks in
// range for such blocks bit array of that block
// is queried
while (l + blk_sz <= r)
{
var idx = k;
for (; idx > 0 ; idx -= idx&-idx)
sum += bit[parseInt(l/blk_sz)][idx];
l += blk_sz;
}
// Traversing the last block
while (l <= r)
{
if (arr[l] <= k)
sum++;
l++;
}
return sum;
}
// Preprocessing the array
function preprocess(arr, blk_sz, n, bit)
{
for (var i=0; i<n; i++)
update(arr[i], parseInt(i/blk_sz), 1, bit);
}
function preprocessUpdate( i, v, blk_sz,
arr, bit)
{
// updating the bit array at the original
// and new value of array
update(arr[i], parseInt(i/blk_sz), -1, bit);
update(v, parseInt(i/blk_sz), 1, bit);
arr[i] = v;
}
// Driver code
// Test Case 1
let arr = [ 5, 1, 2, 3, 4 ];
var n = arr.length;
// size of block size will be equal to square root of n
var blk_sz = parseInt(Math.sqrt(n));
// initialising bit array of each block
// as elements of array cannot exceed 10^4 so size
// of bit array is accordingly
var bit = new Array(blk_sz+1);
for (var i = 0; i < bit.length; i++)
{
bit[i] = new Array(MAX);
}
for (let i = 0; i < bit.length; i++)
{
for (let j = 0; j < MAX; j++)
{
bit[i][j] = 0;
}
}
preprocess(arr, blk_sz, n, bit);
document.write(query (1, 3, 1, arr, blk_sz, bit));
document.write("<br>");
preprocessUpdate(3, 10, blk_sz, arr, bit);
document.write(query(3, 3, 4, arr, blk_sz, bit));
document.write("<br>");
preprocessUpdate(2, 1, blk_sz, arr, bit);
preprocessUpdate(0, 2, blk_sz, arr, bit);
document.write(query (0, 4, 5, arr, blk_sz, bit));
document.write("<br>");
// This code is contributed by Aarti_Rathi
</script>
Producción:
1 0 4
La pregunta es saber por qué no usar este método cuando no hubo operaciones de actualización. La respuesta radica en la complejidad del espacio. En este método, se usa una array de bits 2-d y su tamaño depende del valor máximo posible de la array, pero cuando había ninguna operación de actualización, nuestra array de bits solo dependía del tamaño de la array. Este artículo es una contribución de Ayush Jha . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA