Consultas para el recuento de elementos de suma de dígitos pares en el rango dado usando Segment Tree.

Posted on by Rudeus Greyrat

Dada una array arr[] de N elementos, la tarea es responder Q consultas, cada una de las cuales tiene dos números enteros L y R. Para cada consulta, la tarea es encontrar el número de elementos en el subarreglo arr[L…R] cuya suma de dígitos es par.
Ejemplos: 
 

Entrada: arr[] = {7, 3, 19, 13, 5, 4} 
consulta = { 1, 5 } 
Salida: 3 
Explicación: 
Los elementos 19, 13 y 4 tienen una suma de dígitos pares 
en el subarreglo {3, 9, 13 , 5, 4}.
Entrada: arr[] = {0, 1, 2, 3, 4, 5, 6, 7} 
consulta = { 3, 5 } 
Salida: 1 
Explicación: 
Solo 4 tiene una suma de dígitos pares 
en el subarreglo {3, 4, 5 }. 
 

Enfoque ingenuo: 
 

  • Encuentre la respuesta para cada consulta simplemente recorriendo la array desde el índice L hasta el R y siga agregando 1 al conteo siempre que el elemento de la array tenga una suma de dígitos pares. La complejidad temporal de este enfoque será O(n * q) . 
     

Enfoque eficiente: 
la idea es construir un árbol de segmentos . 
 

  1. Representación de árboles de segmentos: 
    • Los Nodes hoja son los elementos de la array de entrada. 
       
    • Cada Node interno contiene el número de hojas que tiene una suma de dígitos pares de todas las hojas debajo de él. 
       
  2. Construcción del árbol de segmentos a partir de una array dada: 
    • Empezamos con un segmento arr[0 . . . n-1]. y cada vez que dividimos el segmento actual en dos mitades (si aún no se ha convertido en un segmento de longitud 1) y luego llamamos al mismo procedimiento en ambas mitades y para cada segmento, almacenamos el número de elementos que tiene una suma de dígitos pares de todos los Nodes debajo de él. 
       

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

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the digit sum
// for a number
int digitSum(int num)
{
    int sum = 0;
    while (num) {
        sum += (num % 10);
        num /= 10;
    }
 
    return sum;
}
 
// Procedure to build the segment tree
void buildTree(vector<int>& tree, int* arr,
               int index, int s, int e)
{
 
    // Reached the leaf node
    // of the segment tree
    if (s == e) {
        if (digitSum(arr[s]) & 1)
            tree[index] = 0;
        else
            tree[index] = 1;
        return;
    }
 
    // Recursively call the buildTree
    // on both the nodes of the tree
    int mid = (s + e) / 2;
    buildTree(tree, arr, 2 * index,
              s, mid);
    buildTree(tree, arr, 2 * index + 1,
              mid + 1, e);
 
    tree[index] = tree[2 * index]
                + tree[2 * index + 1];
}
 
// Query procedure to get the answer
// for each query l and r are
// query range
int query(vector<int> tree, int index,
          int s, int e, int l, int r)
{
 
    // Out of bound or no overlap
    if (r < s || l > e)
        return 0;
 
    // Complete overlap
    // Query range completely lies in
    // the segment tree node range
    if (s >= l && e <= r) {
        return tree[index];
    }
 
    // Partially overlap
    // Query range partially lies in
    // the segment tree node range
    int mid = (s + e) / 2;
    return (query(tree, 2 * index, s,
                  mid, l, r)
            + query(tree, 2 * index + 1,
                    mid + 1, e, l, r));
}
 
// Driver code
int main()
{
    int arr[] = { 7, 3, 19, 13, 5, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    vector<int> tree(4 * n + 1);
 
    int L = 1, R = 5;
 
    buildTree(tree, arr, 1, 0, n - 1);
 
    cout << query(tree, 1, 0, n - 1, L, R)
         << endl;
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
class GFG{
 
// Function to find the digit sum
// for a number
static int digitSum(int num)
{
    int sum = 0;
    while (num > 0)
    {
        sum += (num % 10);
        num /= 10;
    }
    return sum;
}
 
// Procedure to build the segment tree
static void buildTree(int []tree, int []arr,
                int index, int s, int e)
{
 
    // Reached the leaf node
    // of the segment tree
    if (s == e)
    {
        if (digitSum(arr[s]) % 2 == 1)
            tree[index] = 0;
        else
            tree[index] = 1;
        return;
    }
 
    // Recursively call the buildTree
    // on both the nodes of the tree
    int mid = (s + e) / 2;
    buildTree(tree, arr, 2 * index,
              s, mid);
    buildTree(tree, arr, 2 * index + 1,
              mid + 1, e);
 
    tree[index] = tree[2 * index] +
                    tree[2 * index + 1];
}
 
// Query procedure to get the answer
// for each query l and r are
// query range
static int query(int []tree, int index,
                 int s, int e,
                 int l, int r)
{
 
    // Out of bound or no overlap
    if (r < s || l > e)
        return 0;
 
    // Complete overlap
    // Query range completely lies in
    // the segment tree node range
    if (s >= l && e <= r)
    {
        return tree[index];
    }
 
    // Partially overlap
    // Query range partially lies in
    // the segment tree node range
    int mid = (s + e) / 2;
    return (query(tree, 2 * index, s,
                  mid, l, r) +
            query(tree, 2 * index + 1,
                  mid + 1, e, l, r));
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 7, 3, 19, 13, 5, 4 };
    int n = arr.length;
    int []tree = new int[4 * n + 1];
 
    int L = 1, R = 5;
 
    buildTree(tree, arr, 1, 0, n - 1);
 
    System.out.print(query(tree, 1, 0,
                           n - 1, L, R) + "\n");
}
}
 
// This code is contributed by gauravrajput1

Python3

# Python3 implementation of the above approach
 
# Function to find the digit sum
# for a number
def digitSum(num):
     
    sum = 0;
    while (num):
        sum += (num % 10)
        num //= 10
     
    return sum
 
# Procedure to build the segment tree
def buildTree(tree, arr, index, s, e):
 
    # Reached the leaf node
    # of the segment tree
    if (s == e):
        if (digitSum(arr[s]) & 1):
            tree[index] = 0
        else:
            tree[index] = 1
        return
 
    # Recursively call the buildTree
    # on both the nodes of the tree
    mid = (s + e) // 2
    buildTree(tree, arr, 2 * index,
              s, mid)
    buildTree(tree, arr, 2 * index + 1,
              mid + 1, e)
 
    tree[index] = (tree[2 * index] +
                   tree[2 * index + 1])
 
# Query procedure to get the answer
# for each query l and r are
# query range
def query(tree, index, s, e, l, r):
 
    # Out of bound or no overlap
    if (r < s or l > e):
        return 0
 
    # Complete overlap
    # Query range completely lies in
    # the segment tree node range
    if (s >= l and e <= r):
        return tree[index]
 
    # Partially overlap
    # Query range partially lies in
    # the segment tree node range
    mid = (s + e) // 2
    return (query(tree, 2 * index,
                  s, mid, l, r) +
            query(tree, 2 * index + 1,
                  mid + 1, e, l, r))
 
# Driver code
arr = [ 7, 3, 19, 13, 5, 4 ]
n = len(arr)
 
tree = [0] * (4 * n + 1)
 
L = 1
R = 5
 
buildTree(tree, arr, 1, 0, n - 1);
 
print(query(tree, 1, 0, n - 1, L, R))
 
# This code is contributed by Apurvaraj

C#

// C# implementation of the approach
using System;
class GFG{
 
// Function to find the digit sum
// for a number
static int digitSum(int num)
{
    int sum = 0;
    while (num > 0)
    {
        sum += (num % 10);
        num /= 10;
    }
    return sum;
}
 
// Procedure to build the segment tree
static void buildTree(int []tree, int []arr,
                      int index, int s, int e)
{
 
    // Reached the leaf node
    // of the segment tree
    if (s == e)
    {
        if (digitSum(arr[s]) % 2 == 1)
            tree[index] = 0;
        else
            tree[index] = 1;
        return;
    }
 
    // Recursively call the buildTree
    // on both the nodes of the tree
    int mid = (s + e) / 2;
    buildTree(tree, arr, 2 * index,
              s, mid);
    buildTree(tree, arr, 2 * index + 1,
              mid + 1, e);
 
    tree[index] = tree[2 * index] +
                  tree[2 * index + 1];
}
 
// Query procedure to get the answer
// for each query l and r are
// query range
static int query(int []tree, int index,
                 int s, int e,
                 int l, int r)
{
 
    // Out of bound or no overlap
    if (r < s || l > e)
        return 0;
 
    // Complete overlap
    // Query range completely lies in
    // the segment tree node range
    if (s >= l && e <= r)
    {
        return tree[index];
    }
 
    // Partially overlap
    // Query range partially lies in
    // the segment tree node range
    int mid = (s + e) / 2;
    return (query(tree, 2 * index, s,
                  mid, l, r) +
            query(tree, 2 * index + 1,
                  mid + 1, e, l, r));
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 7, 3, 19, 13, 5, 4 };
    int n = arr.Length;
    int []tree = new int[4 * n + 1];
 
    int L = 1, R = 5;
 
    buildTree(tree, arr, 1, 0, n - 1);
 
    Console.Write(query(tree, 1, 0,
                        n - 1, L, R) + "\n");
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
      // JavaScript implementation of the approach
       
      // Function to find the digit sum
      // for a number
      function digitSum(num) {
        var sum = 0;
        while (num > 0) {
          sum += parseInt(num % 10);
          num = parseInt(num / 10);
        }
        return sum;
      }
 
      // Procedure to build the segment tree
      function buildTree(tree, arr, index, s, e) {
        // Reached the leaf node
        // of the segment tree
        if (s === e) {
          if (digitSum(arr[s]) % 2 === 1) tree[index] = 0;
          else tree[index] = 1;
          return;
        }
 
        // Recursively call the buildTree
        // on both the nodes of the tree
        var mid = parseInt((s + e) / 2);
        buildTree(tree, arr, 2 * index, s, mid);
        buildTree(tree, arr, 2 * index + 1, mid + 1, e);
 
        tree[index] = tree[2 * index] + tree[2 * index + 1];
      }
 
      // Query procedure to get the answer
      // for each query l and r are
      // query range
      function query(tree, index, s, e, l, r) {
        // Out of bound or no overlap
        if (r < s || l > e) return 0;
 
        // Complete overlap
        // Query range completely lies in
        // the segment tree node range
        if (s >= l && e <= r) {
          return tree[index];
        }
 
        // Partially overlap
        // Query range partially lies in
        // the segment tree node range
        var mid = (s + e) / 2;
        return (
          query(tree, 2 * index, s, mid, l, r) +
          query(tree, 2 * index + 1, mid + 1, e, l, r)
        );
      }
 
      // Driver code
      var arr = [7, 3, 19, 13, 5, 4];
      var n = arr.length;
      var tree = new Array(4 * n + 1).fill(0);
 
      var L = 1,
        R = 5;
 
      buildTree(tree, arr, 1, 0, n - 1);
 
      document.write(query(tree, 1, 0, n - 1, L, R) + "<br>");
       
</script>
Producción: 

3

 

Complejidad del tiempo: O(Q * log(N))
 

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 *