Consultas de rango de array binaria para encontrar la distancia mínima entre dos ceros

Posted on by Rudeus Greyrat

Requisito previo: árboles de segmentos
Dada una array binaria arr[] que consta solo de 0 y 1 y una array 2D Q[][] que consta de K consultas, la tarea es encontrar la distancia mínima entre dos 0 en el rango [L, R] de la array para cada consulta {L, R}.

Ejemplos:

Entrada: arr[] = {1, 0, 0, 1}, Q[][] = {{0, 2}} 
Salida: 1 
Explicación: 
Claramente, en el rango [0, 2], el primer 0 se encuentra en índice 1 y último en el índice 2. 
Distancia mínima = 2 – 1 = 1.

Entrada: arr[] = {1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0}, Q[][] = {{3, 9}, { 10, 13}} 
Salida: 2 3 
Explicación: 
En el rango [3, 9], la distancia mínima entre 0 es 2 (Índice 4 y 6). 
En el rango [10, 13], la distancia mínima entre 0 es 3 (Índice 10 y 13). 

Enfoque: La idea es usar un árbol de segmentos para resolver este problema: 

  1. Cada Node en el árbol de segmentos tendrá el índice del 0 más a la izquierda así como el 0 más a la derecha y un número entero que contiene la distancia mínima entre los 0 en el subarreglo {L, R}.
  2. Sea min la distancia mínima entre dos ceros. Luego, el valor de min se puede encontrar después de formar el árbol de segmentos como: 
    min = mínimo (valor de min en el Node izquierdo, el valor de min en el Node derecho y la diferencia entre el índice más a la izquierda de 0 en el Node derecho y índice más a la derecha de 0 en el Node izquierdo).
  3. Después de calcular y almacenar la distancia mínima para cada Node, todas las consultas se pueden responder en tiempo logarítmico.

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

C++

// C++ program to find the minimum 
// distance between two elements 
// with value 0 within a subarray (l, r) 
  
#include <bits/stdc++.h> 
using namespace std; 
  
// Structure for each node 
// in the segment tree 
struct node { 
    int l0, r0; 
    int min0; 
} seg[100001]; 
  
// A utility function for 
// merging two nodes 
node task(node l, node r) 
{ 
    node x; 
  
    x.l0 = (l.l0 != -1) ? l.l0 : r.l0; 
  
    x.r0 = (r.r0 != -1) ? r.r0 : l.r0; 
  
    x.min0 = min(l.min0, r.min0); 
  
    // If both the nodes are valid 
    if (l.r0 != -1 && r.l0 != -1) 
  
        // Computing the minimum distance to store 
        // in the segment tree 
        x.min0 = min(x.min0, r.l0 - l.r0); 
  
    return x; 
} 
  
// A recursive function that constructs 
// Segment Tree for given string 
void build(int qs, int qe, int ind, int arr[]) 
{ 
    // If start is equal to end then 
    // insert the array element 
    if (qs == qe) { 
  
        if (arr[qs] == 0) { 
            seg[ind].l0 = seg[ind].r0 = qs; 
            seg[ind].min0 = INT_MAX; 
        } 
  
        else { 
            seg[ind].l0 = seg[ind].r0 = -1; 
            seg[ind].min0 = INT_MAX; 
        } 
  
        return; 
    } 
  
    int mid = (qs + qe) >> 1; 
  
    // Build the segment tree 
    // for range qs to mid 
    build(qs, mid, ind << 1, arr); 
  
    // Build the segment tree 
    // for range mid+1 to qe 
    build(mid + 1, qe, ind << 1 | 1, arr); 
  
    // Merge the two child nodes 
    // to obtain the parent node 
    seg[ind] = task(seg[ind << 1], 
                    seg[ind << 1 | 1]); 
} 
  
// Query in a range qs to qe 
node query(int qs, int qe, int ns, int ne, int ind) 
{ 
    node x; 
    x.l0 = x.r0 = -1; 
    x.min0 = INT_MAX; 
  
    // If the range lies in this segment 
    if (qs <= ns && qe >= ne) 
        return seg[ind]; 
  
    // If the range is out of the bounds 
    // of this segment 
    if (ne < qs || ns > qe || ns > ne) 
        return x; 
  
    // Else query for the right and left 
    // child node of this subtree 
    // and merge them 
    int mid = (ns + ne) >> 1; 
  
    node l = query(qs, qe, ns, mid, ind << 1); 
    node r = query(qs, qe, mid + 1, ne, ind << 1 | 1); 
  
    x = task(l, r); 
    return x; 
} 
  
// Driver code 
int main() 
{ 
  
    int arr[] = { 1, 1, 0, 1, 0, 1, 
                0, 1, 0, 1, 0, 1, 1, 0 }; 
  
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    // Build the segment tree 
    build(0, n - 1, 1, arr); 
  
    // Queries 
    int Q[][2] = { { 3, 9 }, { 10, 13 } }; 
  
    for (int i = 0; i < 2; i++) { 
  
// Finding the answer for every query 
// and printing it 
        node ans = query(Q[i][0], Q[i][1], 
                        0, n - 1, 1); 
  
        cout << ans.min0 << endl; 
    } 
  
    return 0; 
} 

Java

// Java program to find the minimum
// distance between two elements
// with value 0 within a subarray (l, r)
class GFG{
  
// Structure for each Node
// in the segment tree
static class Node
{
    int l0, r0;
    int min0;
};
  
static Node[] seg = new Node[100001];
  
// A utility function for
// merging two Nodes
static Node task(Node l, Node r) 
{
    Node x = new Node();
  
    x.l0 = (l.l0 != -1) ? l.l0 : r.l0;
  
    x.r0 = (r.r0 != -1) ? r.r0 : l.r0;
  
    x.min0 = Math.min(l.min0, r.min0);
  
    // If both the Nodes are valid
    if (l.r0 != -1 && r.l0 != -1)
  
        // Computing the minimum distance to store
        // in the segment tree
        x.min0 = Math.min(x.min0, r.l0 - l.r0);
  
    return x;
}
  
// A recursive function that constructs
// Segment Tree for given string
static void build(int qs, int qe, 
                  int ind, int arr[])
{
      
    // If start is equal to end then
    // insert the array element
    if (qs == qe)
    {
        if (arr[qs] == 0)
        {
            seg[ind].l0 = seg[ind].r0 = qs;
            seg[ind].min0 = Integer.MAX_VALUE;
        }
  
        else 
        {
            seg[ind].l0 = seg[ind].r0 = -1;
            seg[ind].min0 = Integer.MAX_VALUE;
        }
        return;
    }
  
    int mid = (qs + qe) >> 1;
  
    // Build the segment tree
    // for range qs to mid
    build(qs, mid, ind << 1, arr);
  
    // Build the segment tree
    // for range mid+1 to qe
    build(mid + 1, qe, ind << 1 | 1, arr);
  
    // Merge the two child Nodes
    // to obtain the parent Node
    seg[ind] = task(seg[ind << 1],
                    seg[ind << 1 | 1]);
}
  
// Query in a range qs to qe
static Node query(int qs, int qe, int ns,
                  int ne, int ind) 
{
    Node x = new Node();
    x.l0 = x.r0 = -1;
    x.min0 = Integer.MAX_VALUE;
  
    // If the range lies in this segment
    if (qs <= ns && qe >= ne)
        return seg[ind];
  
    // If the range is out of the bounds
    // of this segment
    if (ne < qs || ns > qe || ns > ne)
        return x;
  
    // Else query for the right and left
    // child Node of this subtree
    // and merge them
    int mid = (ns + ne) >> 1;
  
    Node l = query(qs, qe, ns, mid,
                          ind << 1);
    Node r = query(qs, qe, mid + 1, 
                  ne, ind << 1 | 1);
  
    x = task(l, r);
    return x;
}
  
// Driver code
public static void main(String[] args) 
{
    for(int i = 0; i < 100001; i++)
    {
        seg[i] = new Node();
    }
  
    int arr[] = { 1, 1, 0, 1, 0, 1, 0,
                  1, 0, 1, 0, 1, 1, 0 };
  
    int n = arr.length;
  
    // Build the segment tree
    build(0, n - 1, 1, arr);
  
    // Queries
    int[][] Q = { { 3, 9 }, { 10, 13 } };
  
    for(int i = 0; i < 2; i++)
    {
          
        // Finding the answer for every query
        // and printing it
        Node ans = query(Q[i][0], Q[i][1],
                         0, n - 1, 1);
  
        System.out.println(ans.min0);
    }
}
}
  
// This code is contributed by sanjeev2552

Python3

# Python3 program to find the minimum
# distance between two elements with 
# value 0 within a subarray (l, r)
import sys
   
# Structure for each node
# in the segment tree
class node():
      
    def __init__(self):
          
        self.l0 = 0
        self.r0 = 0
        min0 = 0
          
seg = [node() for i in range(100001)]
   
# A utility function for
# merging two nodes
def task(l, r):
      
    x = node()
        
    x.l0 = l.l0 if (l.l0 != -1) else r.l0
    x.r0 = r.r0 if (r.r0 != -1)  else l.r0
   
    x.min0 = min(l.min0, r.min0)
   
    # If both the nodes are valid
    if (l.r0 != -1 and r.l0 != -1):
   
        # Computing the minimum distance to
        # store in the segment tree
        x.min0 = min(x.min0, r.l0 - l.r0)
   
    return x
   
# A recursive function that constructs
# Segment Tree for given string
def build(qs, qe, ind, arr):
   
    # If start is equal to end then
    # insert the array element
    if (qs == qe):
   
        if (arr[qs] == 0):
            seg[ind].l0 = seg[ind].r0 = qs
            seg[ind].min0 = sys.maxsize
              
        else:
            seg[ind].l0 = seg[ind].r0 = -1
            seg[ind].min0 = sys.maxsize
   
        return
   
    mid = (qs + qe) >> 1
      
    # Build the segment tree
    # for range qs to mid
    build(qs, mid, ind << 1, arr)
   
    # Build the segment tree
    # for range mid+1 to qe
    build(mid + 1, qe, ind << 1 | 1, arr)
   
    # Merge the two child nodes
    # to obtain the parent node
    seg[ind] = task(seg[ind << 1],
                    seg[ind << 1 | 1])
                      
# Query in a range qs to qe
def query(qs, qe, ns, ne, ind):
   
    x = node()
    x.l0 = x.r0 = -1
    x.min0 = sys.maxsize
   
    # If the range lies in this segment
    if (qs <= ns and qe >= ne):
        return seg[ind]
   
    # If the range is out of the bounds
    # of this segment
    if (ne < qs or ns > qe or ns > ne):
        return x
   
    # Else query for the right and left
    # child node of this subtree
    # and merge them
    mid = (ns + ne) >> 1
   
    l = query(qs, qe, ns, mid, ind << 1)
    r = query(qs, qe, mid + 1, ne, ind << 1 | 1)
   
    x = task(l, r)
      
    return x
  
# Driver code  
if __name__=="__main__":
      
    arr = [ 1, 1, 0, 1, 0, 1, 0, 
            1, 0, 1, 0, 1, 1, 0 ]
   
    n = len(arr)
   
    # Build the segment tree
    build(0, n - 1, 1, arr)
      
    # Queries
    Q = [ [ 3, 9 ], [ 10, 13 ] ]
      
    for i in range(2):
   
        # Finding the answer for every query
        # and printing it
        ans = query(Q[i][0], Q[i][1], 0, 
                    n - 1, 1)
          
        print(ans.min0)
  
# This code is contributed by rutvik_56

Producción:

2
3

Tema relacionado: Árbol de segmentos

Publicación traducida automáticamente

Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *