Dada una array arr[] que consta de N enteros y una array 2D Q[][] que consta de consultas de los siguientes dos tipos:
- 1 LR: Imprime el conteo de números del rango [L, R] con un solo bit establecido.
- 2 XV: actualice el elemento de la array en el índice X con V .
Ejemplos:
Entrada: arr[] = { 12, 11, 16, 2, 32 }, Q[][] = { { 1, 0, 2 }, { 2, 4, 24 }, { 1, 1, 4 } }
Salida : 1 2
Explicación:
- Consulta 1: Imprime el recuento de elementos de la array con un solo bit en el rango de índices [0, 2], es decir, {16}.
- Consulta 2: Establecer arr[4] = 24 . Por lo tanto, la array arr[] se modifica a {12, 11, 16, 24, 5}.
- Consulta 3: Imprima el recuento de elementos de array con un solo bit en el rango de índices [1, 4], es decir, {16, 32}.
Entrada: arr[] = { 2, 1, 101, 11, 4 }, Q[][] = { { 1, 2, 4 }, { 2, 4, 12 }, { 1, 2, 4 } }
Salida : 1 0
Explicación:
- Consulta 1: Imprime el recuento de elementos de la array con un solo bit en el rango de índices [2, 4], es decir, {4}.
- Consulta 2: establezca arr[4] = 24 , lo que modifica la array a arr[] = { 2, 1, 101, 11, 12}.
- Consulta 3: imprima el recuento de elementos de array con un solo bit en el rango de índices [2, 4]. Pero ningún elemento de array del rango dado de índices contiene solo un bit.
Enfoque ingenuo: el enfoque más simple es recorrer la array sobre el rango de índices [L, R] para cada consulta y para cada elemento, verificar si tiene exactamente un bit establecido o no. Cuenta de incrementos para cada elemento de la array para el que se encuentra que es verdadero. Después de recorrer todo el rango, imprima el valor de count . Para consultas de tipo 2, simplemente arr[X] = V .
Complejidad de tiempo: O(N * Q * log(N))
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando un árbol de segmentos . Siga los pasos a continuación para resolver el problema:
- Defina una función, marque (S) para verificar si el número entero contiene solo un bit establecido.
- Inicialice 3 variables: ss, se y si para almacenar el punto inicial del segmento actual, el punto final del segmento actual y el valor del Node actual en el árbol del segmento, respectivamente.
- Defina una función, digamos build_seg(ss, se, si), para construir un árbol de segmentos Similar al árbol de segmentos de suma , cada Node almacena el recuento de elementos con un solo bit en su subárbol:
- Si ss == se, árbol[s[i]] = comprobar (arr[ss] )
- De lo contrario, atraviese el subárbol izquierdo y el subárbol derecho.
- Ahora, actualice el Node actual como árbol[si] = árbol[2 * si + 1]+ árbol[2 * si + 2].
- Defina una función, digamos actualizar( ss, se, si, X, V) , para señalar actualizar un valor en la array arr[]:
- Si el Node actual es un Node hoja, es decir, ss == se , actualice el árbol [si] = comprobar (V).
- De lo contrario, busque el índice X , es decir, si X ≤ (ss + se) / 2 , luego vaya al subárbol izquierdo, es decir , actualice (ss, mid, 2 * si + 1, X, V). De lo contrario, vaya al subárbol derecho, es decir , actualice (mid + 1, se, 2 * si + 2, X, V).
- Actualizar el Node actual.
- Defina una función, digamos consulta (ss, se, si, L, R) para contar números que tienen solo un bit en el rango [L, R]:
- Verifique si el segmento actual [L, R] no se cruza con [ss, se] y luego devuelva 0.
- De lo contrario, si ss >= L y se ≤ R , devuelve tree[si] .
- Si ninguna de las condiciones anteriores satisface, devuelve query(ss, mid, L, R, 2 * si + 1)+query(mid + 1, se, L, R, 2 * si + 2) .
- Para consultas de tipo { 1, L, R } , imprima la consulta (0, N-1, 0, L, R).
- Para consultas de tipo { 2, X, V }, actualice el valor en el árbol, actualice (0, N-1, 0, X, V) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation
// for above approach
#include <bits/stdc++.h>
using namespace std;
// Check if N has only
// one set bit
bool check(int N)
{
if (N == 0)
return 0;
return !(N & (N - 1));
}
// Function to build segment tree
void build_seg_tree(int ss, int se, int si,
int tree[], int arr[])
{
// If se is leaf node
if (ss == se) {
// Update the node
tree[si] = check(arr[ss]);
return;
}
// Stores mid value of segment [ss, se]
int mid = (ss + se) / 2;
// Recursive call for left Subtree
build_seg_tree(ss, mid,
2 * si + 1, tree, arr);
// Recursive call for right Subtree
build_seg_tree(mid + 1, se,
2 * si + 2, tree, arr);
// Update the Current Node
tree[si] = tree[2 * si + 1]
+ tree[2 * si + 2];
}
// Function to update a value at Xth index
void update(int ss, int se, int si,
int X, int V, int tree[], int arr[])
{
if (ss == se) {
// If ss is equal to X
if (ss == X) {
// Update the Xth node
arr[X] = V;
// Update the tree
tree[si] = check(V);
}
return;
}
// Stores the mid of segment [ss, se]
int mid = (ss + se) / 2;
if (X <= mid)
update(ss, mid, 2 * si + 1,
X, V, tree, arr);
else
update(mid + 1, se, 2 * si + 2,
X, V, tree, arr);
// Update current node
tree[si] = tree[2 * si + 1]
+ tree[2 * si + 2];
}
// Count of numbers
// having one set bit
int query(int l, int r, int ss,
int se, int si, int tree[])
{
// If L > se or R < ss
// Invalid Range
if (r < ss || l > se)
return 0;
// If [ss, se] lies
// inside the [L, R]
if (l <= ss && r >= se)
return tree[si];
// Stores the mid of segment [ss, se]
int mid = (ss + se) / 2;
// Return the sum after recursively
// traversing left and right subtree
return query(l, r, ss,
mid, 2 * si + 1, tree)
+ query(l, r, mid + 1,
se, 2 * si + 2, tree);
}
// Function to solve queries
void Query(int arr[], int N,
vector<vector<int> > Q)
{
// Initialise Segment tree
int tree[4 * N] = { 0 };
// Build segment tree
build_seg_tree(0, N - 1, 0, tree, arr);
// Perform queries
for (int i = 0; i < (int)Q.size(); i++) {
if (Q[i][0] == 1)
cout << query(Q[i][1], Q[i][2],
0, N - 1, 0, tree)
<< " ";
else
update(0, N - 1, 0, Q[i][1], Q[i][2], tree,
arr);
}
}
// Driver Code
int main()
{
// Input
int arr[] = { 12, 11, 16, 2, 32 };
vector<vector<int> > Q{ { 1, 0, 2 },
{ 2, 4, 24 },
{ 1, 1, 4 } };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call to
// solve queries
Query(arr, N, Q);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
// Check if N has only
// one set bit
static int check(int N)
{
if (Integer.bitCount(N) == 1)
return 1;
else
return 0;
}
// Function to build segment tree
static void build_seg_tree(int ss, int se, int si,
int tree[], int arr[])
{
// If se is leaf node
if (ss == se)
{
// Update the node
tree[si] = check(arr[ss]);
return;
}
// Stores mid value of segment [ss, se]
int mid = (ss + se) / 2;
// Recursive call for left Subtree
build_seg_tree(ss, mid, 2 * si + 1, tree, arr);
// Recursive call for right Subtree
build_seg_tree(mid + 1, se, 2 * si + 2, tree, arr);
// Update the Current Node
tree[si] = tree[2 * si + 1] + tree[2 * si + 2];
}
// Function to update a value at Xth index
static void update(int ss, int se, int si, int X, int V,
int tree[], int arr[])
{
if (ss == se)
{
// If ss is equal to X
if (ss == X)
{
// Update the Xth node
arr[X] = V;
// Update the tree
tree[si] = check(V);
}
return;
}
// Stores the mid of segment [ss, se]
int mid = (ss + se) / 2;
if (X <= mid)
update(ss, mid, 2 * si + 1, X, V, tree, arr);
else
update(mid + 1, se, 2 * si + 2, X, V, tree,
arr);
// Update current node
tree[si] = tree[2 * si + 1] + tree[2 * si + 2];
}
// Count of numbers
// having one set bit
static int query(int l, int r, int ss,
int se, int si,
int tree[])
{
// If L > se or R < ss
// Invalid Range
if (r < ss || l > se)
return 0;
// If [ss, se] lies
// inside the [L, R]
if (l <= ss && r >= se)
return tree[si];
// Stores the mid of segment [ss, se]
int mid = (ss + se) / 2;
// Return the sum after recursively
// traversing left and right subtree
return query(l, r, ss, mid, 2 * si + 1, tree)
+ query(l, r, mid + 1, se, 2 * si + 2, tree);
}
// Function to solve queries
static void Query(int arr[], int N, int[][] Q)
{
// Initialise Segment tree
int tree[] = new int[4 * N];
// Build segment tree
build_seg_tree(0, N - 1, 0, tree, arr);
// Perform queries
for (int i = 0; i < Q.length; i++) {
if (Q[i][0] == 1)
System.out.print(query(Q[i][1], Q[i][2], 0,
N - 1, 0, tree) + " ");
else
update(0, N - 1, 0, Q[i][1], Q[i][2], tree,
arr);
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 12, 11, 16, 2, 32 };
int[][] Q
= { { 1, 0, 2 }, { 2, 4, 24 }, { 1, 1, 4 } };
int N = arr.length;
// Function call to
// solve queries
Query(arr, N, Q);
}
}
// This code is contributed by hemanthsawarna1506.
Python3
# Python3 implementation of # the above approach # Check if N has only # one set bit def check(N) : if (N == 0): return 0 return ((N & (N - 1)) == 0) # Function to build segment tree def build_seg_tree(ss, se, si, tree, arr) : # If se is leaf node if (ss == se) : # Update the node tree[si] = check(arr[ss]) return # Stores mid value of segment [ss, se] mid = (ss + se) // 2 # Recursive call for left Subtree build_seg_tree(ss, mid, 2 * si + 1, tree, arr) # Recursive call for right Subtree build_seg_tree(mid + 1, se, 2 * si + 2, tree, arr) # Update the Current Node tree[si] = tree[2 * si + 1] + tree[2 * si + 2] # Function to update a value at Xth index def update(ss, se, si, X, V, tree, arr) : if (ss == se) : # If ss is equal to X if (ss == X) : # Update the Xth node arr[X] = V # Update the tree tree[si] = check(V) return # Stores the mid of segment [ss, se] mid = (ss + se) // 2 if (X <= mid): update(ss, mid, 2 * si + 1, X, V, tree, arr) else : update(mid + 1, se, 2 * si + 2, X, V, tree, arr) # Update current node tree[si] = tree[2 * si + 1] + tree[2 * si + 2] # Count of numbers # having one set bit def query(l, r, ss, se, si, tree) : # If L > se or R < ss # Invalid Range if (r < ss or l > se): return 0 # If [ss, se] lies # inside the [L, R] if (l <= ss and r >= se): return tree[si] # Stores the mid of segment [ss, se] mid = (ss + se) // 2 # Return the sum after recursively # traversing left and right subtree return (query(l, r, ss, mid, 2 * si + 1, tree) + query(l, r, mid + 1, se, 2 * si + 2, tree)) # Function to solve queries def Query(arr, N, Q) : # Initialise Segment tree tree = [0] * (4 * N) # Build segment tree build_seg_tree(0, N - 1, 0, tree, arr) # Perform queries for i in range(len(Q)): if (Q[i][0] == 1): print(query(Q[i][1], Q[i][2], 0, N - 1, 0, tree), end = " ") else : update(0, N - 1, 0, Q[i][1], Q[i][2], tree, arr) # Driver Code # Input arr = [ 12, 11, 16, 2, 32 ] Q = [ [ 1, 0, 2 ], [ 2, 4, 24 ], [ 1, 1, 4 ]] N = len(arr) # Function call to # solve queries Query(arr, N, Q) # This code is contributed by code_hunt.
C#
// C# implementation
// for above approach
using System;
using System.Collections.Generic;
class GFG
{
// Check if N has only
// one set bit
static int check(int N)
{
if (N == 0 || (N & (N - 1)) != 0)
return 0;
return 1;
}
// Function to build segment tree
static void build_seg_tree(int ss, int se, int si,
int[] tree, int[] arr)
{
// If se is leaf node
if (ss == se)
{
// Update the node
tree[si] = check(arr[ss]);
return;
}
// Stores mid value of segment [ss, se]
int mid = (ss + se) / 2;
// Recursive call for left Subtree
build_seg_tree(ss, mid,
2 * si + 1, tree, arr);
// Recursive call for right Subtree
build_seg_tree(mid + 1, se,
2 * si + 2, tree, arr);
// Update the Current Node
tree[si] = tree[2 * si + 1]
+ tree[2 * si + 2];
}
// Function to update a value at Xth index
static void update(int ss, int se, int si,
int X, int V, int[] tree, int[] arr)
{
if (ss == se)
{
// If ss is equal to X
if (ss == X)
{
// Update the Xth node
arr[X] = V;
// Update the tree
tree[si] = check(V);
}
return;
}
// Stores the mid of segment [ss, se]
int mid = (ss + se) / 2;
if (X <= mid)
update(ss, mid, 2 * si + 1,
X, V, tree, arr);
else
update(mid + 1, se, 2 * si + 2,
X, V, tree, arr);
// Update current node
tree[si] = tree[2 * si + 1]
+ tree[2 * si + 2];
}
// Count of numbers
// having one set bit
static int query(int l, int r, int ss,
int se, int si, int[] tree)
{
// If L > se or R < ss
// Invalid Range
if (r < ss || l > se)
return 0;
// If [ss, se] lies
// inside the [L, R]
if (l <= ss && r >= se)
return tree[si];
// Stores the mid of segment [ss, se]
int mid = (ss + se) / 2;
// Return the sum after recursively
// traversing left and right subtree
return query(l, r, ss,
mid, 2 * si + 1, tree)
+ query(l, r, mid + 1,
se, 2 * si + 2, tree);
}
// Function to solve queries
static void Query(int[] arr, int N,
List<List<int> > Q)
{
// Initialise Segment tree
int[] tree = new int[4 * N];
// Build segment tree
build_seg_tree(0, N - 1, 0, tree, arr);
// Perform queries
for (int i = 0; i < (int)Q.Count; i++)
{
if (Q[i][0] == 1)
Console.Write(query(Q[i][1], Q[i][2], 0, N - 1, 0, tree) + " ");
else
update(0, N - 1, 0, Q[i][1], Q[i][2], tree, arr);
}
}
// Driver code
static void Main()
{
// Input
int[] arr = { 12, 11, 16, 2, 32 };
List<List<int> > Q = new List<List<int>>();
Q.Add(new List<int>(new int[]{1, 0, 2}));
Q.Add(new List<int>(new int[]{2, 4, 24}));
Q.Add(new List<int>(new int[]{1, 1, 4}));
int N = arr.Length;
// Function call to
// solve queries
Query(arr, N, Q);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// JavaScript implementation
// for above approach
// Check if N has only
// one set bit
function check( N)
{
if (N == 0)
return 0;
return !(N & (N - 1));
}
// Function to build segment tree
function build_seg_tree( ss, se, si, tree, arr)
{
// If se is leaf node
if (ss == se) {
// Update the node
tree[si] = check(arr[ss]);
return;
}
// Stores mid value of segment [ss, se]
var mid = parseInt((ss + se) / 2);
// Recursive call for left Subtree
build_seg_tree(ss, mid, 2 * si + 1, tree, arr);
// Recursive call for right Subtree
build_seg_tree(mid + 1, se, 2 * si + 2, tree, arr);
// Update the Current Node
tree[si] = tree[2 * si + 1] + tree[2 * si + 2];
}
// Function to update a value at Xth index
function update(ss, se, si, X, V, tree, arr)
{
if (ss == se) {
// If ss is equal to X
if (ss == X) {
// Update the Xth node
arr[X] = V;
// Update the tree
tree[si] = check(V);
}
return;
}
// Stores the mid of segment [ss, se]
var mid = parseInt((ss + se) / 2);
if (X <= mid)
update(ss, mid, 2 * si + 1, X, V, tree, arr);
else
update(mid + 1, se, 2 * si + 2, X, V, tree, arr);
// Update current node
tree[si] = tree[2 * si + 1] + tree[2 * si + 2];
}
// Count of numbers
// having one set bit
function query( l, r, ss, se, si, tree)
{
// If L > se or R < ss
// Invalid Range
if (r < ss || l > se)
return 0;
// If [ss, se] lies
// inside the [L, R]
if (l <= ss && r >= se)
return tree[si];
// Stores the mid of segment [ss, se]
var mid = parseInt((ss + se) / 2);
// Return the sum after recursively
// traversing left and right subtree
return query(l, r, ss, mid, 2 * si + 1, tree)
+ query(l, r, mid + 1, se, 2 * si + 2, tree);
}
// Function to solve queries
function Query(arr, N, Q)
{
// Initialise Segment tree
var tree = new Array(4 * N);
tree.fill( 0 );
// Build segment tree
build_seg_tree(0, N - 1, 0, tree, arr);
// Perform queries
for (var i = 0; i < Q.length; i++) {
if (Q[i][0] == 1)
document.write( query(Q[i][1], Q[i][2],
0, N - 1, 0, tree)
+ " ");
else
update(0, N - 1, 0, Q[i][1], Q[i][2], tree,
arr);
}
}
var arr = [ 12, 11, 16, 2, 32 ];
var Q = [ [1, 0, 2 ],
[ 2, 4, 24],
[ 1, 1, 4 ] ];
var N = arr.length;
// Function call to
// solve queries
Query(arr, N, Q);
// This code is contributed by SoumikMondal
</script>
Producción:
1 2
Complejidad de tiempo: O(N*log(N)+Q*log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por prakersh009 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA