Consultas para verificar si un dígito dado está presente en el Rango dado

Prerrequisitos: Árbol de segmentos Dada una array de dígitos arr[] . Dado un número de rango [L, R] y un dígito X con cada rango. La tarea es verificar para cada rango dado [L, R] si el dígito X está presente dentro de ese rango en la array arr[]. Ejemplos:

Input : arr = [1, 3, 3, 9, 8, 7]
        l1=0, r1=3, x=2   // Range 1
        l1=2, r1=5, x=3   // Range 2
Output : NO  
         YES
For Range 1: The digit 2 is not present within
             range [0, 3] in the array.
For Range 2: The digit 3 is present within the range
             [2, 5] at index 2 in the given array.

Enfoque ingenuo : un enfoque ingenuo es atravesar cada uno de los rangos dados de los dígitos en la array y verificar si el dígito está presente o no. Complejidad de Tiempo: O(N) para cada consulta. Mejor enfoque : un mejor enfoque es utilizar el árbol de segmentos . Dado que solo hay 10 dígitos posibles de (0-9), cada Node del árbol de segmentos contendrá todos los dígitos dentro del rango de ese Node. Usaremos el conjuntoEstructura de datos en cada Node para almacenar los dígitos. Set es una estructura de datos especial que elimina elementos redundantes y los almacena en orden ascendente. Hemos utilizado una estructura de datos establecida ya que será más fácil fusionar 2 Nodes secundarios para obtener el Node principal en el árbol de segmentos. Insertaremos todos los dígitos presentes en los Nodes secundarios en el conjunto principal y eliminará automáticamente los dígitos redundantes. Por lo tanto, en cada conjunto (Node) habrá un máximo de 10 elementos (0-9 todos los dígitos). También hay una función de conteo incorporada que devuelve el conteo del elemento presente en el conjunto que será útil en la función de consulta para verificar si un dígito está presente en el Node o no. Si el conteo será mayor que 0, eso significa que el elemento está presente en el conjunto, devolveremos verdadero; de lo contrario, devolveremos falso. A continuación se muestra la implementación del enfoque anterior: 

// CPP program to answer Queries to check whether
// a given digit is present in the given range
 
#include <bits/stdc++.h>
using namespace std;
 
#define N 6
 
// Segment Tree with set at each node
set<int> Tree[6 * N];
 
// Function to build the segment tree
void buildTree(int* arr, int idx, int s, int e)
{
    if (s == e) {
        Tree[idx].insert(arr[s]);
        return;
    }
 
    int mid = (s + e) >> 1;
 
    // Left child node
    buildTree(arr, 2 * idx, s, mid);
 
    // Right child node
    buildTree(arr, 2 * idx + 1, mid + 1, e);
 
    // Merging child nodes to get parent node.
    // Since set is used, it will remove
    // redundant digits.
    for (auto it : Tree[2 * idx]) {
        Tree[idx].insert(it);
    }
    for (auto it : Tree[2 * idx + 1]) {
        Tree[idx].insert(it);
    }
}
 
// Function to query a range
bool query(int idx, int s, int e, int qs, int qe, int x)
{
    // Complete Overlap condition
    // return true if digit is present.
    // else false.
    if (qs <= s && e <= qe) {
        if (Tree[idx].count(x) != 0) {
            return true;
        }
        else
            return false;
    }
 
    // No Overlap condition
    // Return false
    if (qe < s || e < qs) {
        return false;
    }
 
    int mid = (s + e) >> 1;
 
    // If digit is found in any child
    // return true, else False
    bool LeftAns = query(2 * idx, s, mid, qs, qe, x);
    bool RightAns = query(2 * idx + 1, mid + 1, e, qs, qe, x);
 
    return LeftAns or RightAns;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 3, 3, 9, 8, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Build the tree
    buildTree(arr, 1, 0, n - 1);
 
    int l, r, x;
 
    // Query 1
    l = 0, r = 3, x = 2;
    if (query(1, 0, n - 1, l, r, x))
        cout << "YES" << '\n';
    else
        cout << "NO" << '\n';
 
    // Query 2
    l = 2, r = 5, x = 3;
    if (query(1, 0, n - 1, l, r, x))
        cout << "YES" << '\n';
    else
        cout << "NO" << '\n';
 
    return 0;
}

// Java program to answer Queries to check whether
// a given digit is present in the given range
import java.io.*;
import java.util.*;
 
class GFG
{
    static int N = 6;
 
    // Segment Tree with set at each node
    @SuppressWarnings("unchecked")
    static HashSet<Integer>[] Tree = new HashSet[6 * N];
    static
    {
        for (int i = 0; i < 6 * N; i++)
            Tree[i] = new HashSet<>();
    }
 
    // Function to build the segment tree
    static void buildTree(int[] arr, int idx, int s, int e)
    {
        if (s == e)
        {
            Tree[idx].add(arr[s]);
            return;
        }
 
        int mid = (s + e) / 2;
 
        // Left child node
        buildTree(arr, 2 * idx, s, mid);
 
        // Right child node
        buildTree(arr, 2 * idx + 1, mid + 1, e);
 
        // Merging child nodes to get parent node.
        // Since set is used, it will remove
        // redundant digits.
        for (int it : Tree[2 * idx])
            Tree[idx].add(it);
        for (int it : Tree[2 * idx + 1])
            Tree[idx].add(it);
    }
 
    // Function to query a range
    static boolean query(int idx, int s, int e,
                        int qs, int qe, int x)
    {
 
        // Complete Overlap condition
        // return true if digit is present.
        // else false.
        if (qs <= s && e <= qe)
        {
            if (Collections.frequency(Tree[idx], x) != 0)
                return true;
            else
                return false;
        }
 
        // No Overlap condition
        // Return false
        if (qe < s || e < qs)
            return false;
 
        int mid = (s + e) / 2;
 
        // If digit is found in any child
        // return true, else False
        boolean LeftAns = query(2 * idx, s, mid, qs, qe, x);
        boolean RightAns = query(2 * idx + 1, mid + 1, e, qs, qe, x);
 
        return (LeftAns || RightAns);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        int[] arr = { 1, 3, 3, 9, 8, 7 };
        int n = arr.length;
 
        // Build the tree
        buildTree(arr, 1, 0, n - 1);
 
        int l, r, x;
 
        // Query 1
        l = 0;
        r = 3;
        x = 2;
        if (query(1, 0, n - 1, l, r, x))
            System.out.println("Yes");
        else
            System.out.println("No");
 
        // Query 2
        l = 2;
        r = 5;
        x = 3;
        if (query(1, 0, n - 1, l, r, x))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
 
// This code is contributed by
// sanjeev2552

# Python3 program to answer Queries to check whether
# a given digit is present in the given range
N = 6
 
# Segment Tree with set at each node
Tree = [0] * (6 * N)
for i in range(6 * N):
    Tree[i] = set()
 
# Function to build the segment tree
def buildTree(arr: list, idx: int,
                   s: int, e: int) -> None:
    global Tree
    if s == e:
        Tree[idx].add(arr[s])
        return
 
    mid = (s + e) // 2
 
    # Left child node
    buildTree(arr, 2 * idx, s, mid)
 
    # Right child node
    buildTree(arr, 2 * idx + 1, mid + 1, e)
 
    # Merging child nodes to get parent node.
    # Since set is used, it will remove
    # redundant digits.
    for it in Tree[2 * idx]:
        Tree[idx].add(it)
 
    for it in Tree[2 * idx + 1]:
        Tree[idx].add(it)
 
# Function to query a range
def query(idx: int, s: int, e: int,
          qs: int, qe: int, x: int) -> bool:
    global Tree
 
    # Complete Overlap condition
    # return true if digit is present.
    # else false.
    if qs <= s and e <= qe:
        if list(Tree[idx]).count(x) != 0:
            return True
        else:
            return False
 
    # No Overlap condition
    # Return false
    if qe < s or e < qs:
        return False
 
    mid = (s + e) // 2
 
    # If digit is found in any child
    # return true, else False
    leftAns = query(2 * idx, s, mid, qs, qe, x)
    rightAns = query(2 * idx + 1,
                         mid + 1, e, qs, qe, x)
 
    return (leftAns or rightAns)
 
# Driver Code
if __name__ == "__main__":
    arr = [1, 3, 3, 9, 8, 7]
    n = len(arr)
 
    # Build the tree
    buildTree(arr, 1, 0, n - 1)
 
    # Query 1
    l = 0
    r = 3
    x = 2
    if query(1, 0, n - 1, l, r, x):
        print("YES")
    else:
        print("NO")
 
    # Query 2
    l = 2
    r = 5
    x = 3
    if query(1, 0, n - 1, l, r, x):
        print("YES")
    else:
        print("NO")
 
# This code is contributed by
# sanjeev2552

// C# program to answer Queries to check whether
// a given digit is present in the given range
using System;
using System.Collections.Generic;
 
class GFG
{
    static int N = 6;
 
    // Segment Tree with set at each node
    static SortedSet<int>[] Tree = new SortedSet<int>[6 * N];
 
    // Function to build the segment tree
    static void buildTree(int[] arr, int idx, int s, int e)
    {
        if (s == e)
        {
            Tree[idx].Add(arr[s]);
            return;
        }
 
        int mid = (s + e) / 2;
 
        // Left child node
        buildTree(arr, 2 * idx, s, mid);
 
        // Right child node
        buildTree(arr, 2 * idx + 1, mid + 1, e);
 
        // Merging child nodes to get parent node.
        // Since set is used, it will remove
        // redundant digits.
        foreach (int it in Tree[2 * idx])
            Tree[idx].Add(it);
        foreach (int it in Tree[2 * idx + 1])
            Tree[idx].Add(it);
    }
 
    // Function to query a range
    static bool query(int idx, int s, int e,
                        int qs, int qe, int x)
    {
 
        // Complete Overlap condition
        // return true if digit is present.
        // else false.
        if (qs <= s && e <= qe)
        {
            if (Tree[idx].Contains(x))
                return true;
            else
                return false;
        }
 
        // No Overlap condition
        // Return false
        if (qe < s || e < qs)
            return false;
 
        int mid = (s + e) / 2;
 
        // If digit is found in any child
        // return true, else False
        bool LeftAns = query(2 * idx, s, mid, qs, qe, x);
        bool RightAns = query(2 * idx + 1, mid + 1, e, qs, qe, x);
 
        return (LeftAns || RightAns);
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
 
        int[] arr = { 1, 3, 3, 9, 8, 7 };
        int n = arr.Length;
        for (int i = 0; i < 6 * N; i++)
            Tree[i] = new SortedSet<int>();
         
        // Build the tree
        buildTree(arr, 1, 0, n - 1);
 
        int l, r, x;
 
        // Query 1
        l = 0;
        r = 3;
        x = 2;
        if (query(1, 0, n - 1, l, r, x))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
 
        // Query 2
        l = 2;
        r = 5;
        x = 3;
        if (query(1, 0, n - 1, l, r, x))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}
 
// This code is contributed by Rajput-Ji

NO
YES

Complejidad de tiempo: O(N) una vez para construir el árbol de segmentos, luego O(logN) para cada consulta.