Consultas de rango para encontrar el elemento que tiene la suma máxima de dígitos

Dada una array Arr de N enteros y Q consultas, cada consulta tiene un rango de L a R. Encuentre el elemento que tiene la suma máxima de dígitos para el rango L a R, y si más de un elemento tiene una suma máxima de dígitos, busque el elemento máximo de esos.
Ejemplos: 

Input: Arr[] = { 16, 12, 43, 55} 
       Q = 2
       L = 0, R = 3
       L = 0, R = 2

Output: 55
        43

Explanation:
 The range (0, 3) in the 1st query has
 [16, 12, 43, 55]. Here, the digit sums are:
 for 16, 1 + 6 = 7
 for 12, 1 + 2 = 3
 for 43, 4 + 3 = 7
 for 55, 5 + 5 = 10
 Hence, the max digit sum is 10 and 
 max digit sum value is 55.

 The range (0, 2) in the 1st query has
 [16, 12, 43]. Here, the digit sums are:
 for 16, 1 + 6 = 7
 for 12, 1 + 2 = 3
 for 43, 4 + 3 = 7
 Hence, the max digit sum is 7 and 
 max digit sum value is max( 16, 43) = 43. 

Enfoque ingenuo: 
una solución simple es ejecutar un ciclo de L a R y calcular la suma de dígitos para cada elemento y encontrar el elemento de suma de dígitos máximo de L a R para cada consulta.

Complejidad de tiempo : O(Q * N), 
Espacio auxiliar : O(1)

Enfoque eficiente:  

• Un enfoque eficiente será construir un árbol de segmentos donde cada Node almacene dos valores ( value y max_digit_sum ), y hacer una consulta de rango en él para encontrar la suma máxima de dígitos y el elemento correspondiente. Pero para construir el árbol de segmentos tenemos que pensar qué almacenar en los Nodes del árbol.
• Para averiguar el valor máximo de la suma de dígitos, necesitaremos dos cosas, una es el valor y la otra suma de dígitos. La fusión devolverá dos cosas, la suma de dígitos almacenará el máximo (max_digit_sum.left, max_digit_sum.right) en el árbol de segmentos y el valor contendrá el valor del elemento correspondiente.
• Si lo analizamos en profundidad, la suma máxima de dígitos para cualquier combinación de dos rangos será la suma máxima de dígitos del lado izquierdo o la suma máxima de dígitos del lado derecho, lo que sea máximo se tendrá en cuenta.
• Representación de árboles de segmentos: 
  1. Los Nodes hoja son los elementos de la array dada.
  2. Cada Node interno representa alguna fusión de los Nodes hoja. La fusión puede ser diferente para diferentes problemas. Para este problema, la fusión es el máximo de max_digit_sum de hojas debajo de un Node.
  3. Se utiliza una representación de array del árbol para representar los árboles de segmento. Para cada Node en el índice i, el hijo izquierdo está en el índice 2*i+1 , el hijo derecho en 2*i+2 y el padre está en (i-1)/2 . 
      
• Construcción de un árbol de segmentos a partir de una array dada: 
  1. 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 uno de esos segmentos, almacenamos max_digit_sum y el valor en el Node correspondiente.
  2. Luego hacemos una consulta de rango en el árbol de segmentos para averiguar max_digit_sum para el rango dado y mostrar el valor correspondiente.

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

// C++ program to find
// maximum digit sum value
#include <bits/stdc++.h>
using namespace std;
 
// Struct two store two values in one node
struct Node {
    int value;
    int max_digit_sum;
};
 
Node tree[4 * 10000];
 
// Function to find the digit sum
// for a number
int digitSum(int x)
{
    int sum = 0;
    while (x) {
        sum += (x % 10);
        x /= 10;
    }
}
 
// Function to build the segment tree
void build(int a[], int index, int beg, int end)
{
    if (beg == end) {
 
        // If there is one element in array,
        tree[index].value = a[beg];
        tree[index].max_digit_sum = digitSum(a[beg]);
    }
    else {
 
        int mid = (beg + end) / 2;
 
        // If there are more than one elements,
        // then recur for left and right subtrees
        build(a, 2 * index + 1, beg, mid);
        build(a, 2 * index + 2, mid + 1, end);
 
        if (tree[2 * index + 1].max_digit_sum >
            tree[2 * index + 2].max_digit_sum)
        {
            tree[index].max_digit_sum =
                tree[2 * index + 1].max_digit_sum;
            tree[index].value =
                tree[2 * index + 1].value;
        }
        else if (tree[2 * index + 2].max_digit_sum >
                 tree[2 * index + 1].max_digit_sum)
        {
            tree[index].max_digit_sum =
                tree[2 * index + 2].max_digit_sum;
            tree[index].value =
                tree[2 * index + 2].value;
        }
        else
        {
            tree[index].max_digit_sum =
                tree[2 * index + 2].max_digit_sum;
            tree[index].value =
                max(tree[2 * index + 2].value,
                    tree[2 * index + 1].value);
        }
    }
}
 
// Function to do the range query in the segment
// tree for the maximum digit sum
Node query(int index, int beg, int end,
           int l, int r)
{
    Node result;
    result.value = result.max_digit_sum = -1;
 
    // If segment of this node is outside the given
    // range, then return the minimum value.
    if (beg > r || end < l)
        return result;
 
    // If segment of this node is a part of given
    // range, then return the node of the segment
    if (beg >= l && end <= r)
        return tree[index];
 
    int mid = (beg + end) / 2;
 
    // If left segment of this node falls out of
    // range, then recur in the right side of
    // the tree
    if (l > mid)
        return query(2 * index + 2, mid + 1,
                     end, l, r);
 
    // If right segment of this node falls out of
    // range, then recur in the left side of
    // the tree
    if (r <= mid)
        return query(2 * index + 1, beg,
                     mid, l, r);
 
    // If a part of this segment overlaps with
    // the given range
    Node left = query(2 * index + 1, beg,
                      mid, l, r);
    Node right = query(2 * index + 2, mid + 1,
                       end, l, r);
 
    if (left.max_digit_sum > right.max_digit_sum)
    {
        result.max_digit_sum = left.max_digit_sum;
        result.value = left.value;
    }
    else if (right.max_digit_sum > left.max_digit_sum)
    {
        result.max_digit_sum = right.max_digit_sum;
        result.value = right.value;
    }
    else
    {
        result.max_digit_sum = left.max_digit_sum;
        result.value = max(right.value, left.value);
    }
 
    // Returns the value
    return result;
}
 
// Driver code
int main()
{
 
    int a[] = {16, 12, 43, 55};
 
    // Calculates the length of array
    int N = sizeof(a) / sizeof(a[0]);
 
    // Calls the build function to build
    // the segment tree
    build(a, 0, 0, N - 1);
 
    // Find the max digit-sum value between
    // 0th and 3rd index of array
    cout << query(0, 0, N - 1, 0, 3).value
         << endl;
 
    // Find the max digit-sum value between
    // 0th and 2nd index of array
    cout << query(0, 0, N - 1, 0, 2).value
         << endl;
 
    return 0;
}

// Java program to find
// maximum digit sum value
import java.util.*;
 
class GFG{
 
// Struct two store two values
// in one node
static class Node
{
    int value;
    int max_digit_sum;
};
 
static Node []tree = new Node[4 * 10000];
 
// Function to find the digit sum
// for a number
static int digitSum(int x)
{
    int sum = 0;
     
    while (x > 0)
    {
        sum += (x % 10);
        x /= 10;
    }
    return sum;
}
 
// Function to build the segment tree
static void build(int a[], int index,
                  int beg, int end)
{
    if (beg == end)
    {
         
        // If there is one element in array,
        tree[index].value = a[beg];
        tree[index].max_digit_sum = digitSum(a[beg]);
    }
    else
    {
        int mid = (beg + end) / 2;
 
        // If there are more than one elements,
        // then recur for left and right subtrees
        build(a, 2 * index + 1, beg, mid);
        build(a, 2 * index + 2, mid + 1, end);
 
        if (tree[2 * index + 1].max_digit_sum >
            tree[2 * index + 2].max_digit_sum)
        {
            tree[index].max_digit_sum =
                tree[2 * index + 1].max_digit_sum;
            tree[index].value =
                tree[2 * index + 1].value;
        }
        else if (tree[2 * index + 2].max_digit_sum >
                 tree[2 * index + 1].max_digit_sum)
        {
            tree[index].max_digit_sum =
                tree[2 * index + 2].max_digit_sum;
            tree[index].value =
                tree[2 * index + 2].value;
        }
        else
        {
            tree[index].max_digit_sum =
                tree[2 * index + 2].max_digit_sum;
            tree[index].value =
                Math.max(tree[2 * index + 2].value,
                         tree[2 * index + 1].value);
        }
    }
}
 
// Function to do the range query in the segment
// tree for the maximum digit sum
static Node query(int index, int beg, int end,
                  int l, int r)
{
    Node result = new Node();
    result.value = result.max_digit_sum = -1;
 
    // If segment of this node is outside the given
    // range, then return the minimum value.
    if (beg > r || end < l)
        return result;
 
    // If segment of this node is a part of given
    // range, then return the node of the segment
    if (beg >= l && end <= r)
        return tree[index];
 
    int mid = (beg + end) / 2;
 
    // If left segment of this node falls out of
    // range, then recur in the right side of
    // the tree
    if (l > mid)
        return query(2 * index + 2, mid + 1,
                     end, l, r);
 
    // If right segment of this node falls out of
    // range, then recur in the left side of
    // the tree
    if (r <= mid)
        return query(2 * index + 1, beg,
                     mid, l, r);
 
    // If a part of this segment overlaps with
    // the given range
    Node left = query(2 * index + 1, beg,
                      mid, l, r);
    Node right = query(2 * index + 2, mid + 1,
                       end, l, r);
 
    if (left.max_digit_sum > right.max_digit_sum)
    {
        result.max_digit_sum = left.max_digit_sum;
        result.value = left.value;
    }
    else if (right.max_digit_sum > left.max_digit_sum)
    {
        result.max_digit_sum = right.max_digit_sum;
        result.value = right.value;
    }
    else
    {
        result.max_digit_sum = left.max_digit_sum;
        result.value = Math.max(right.value,
                                 left.value);
    }
 
    // Returns the value
    return result;
}
 
// Driver code
public static void main(String[] args)
{
    int a[] = { 16, 12, 43, 55 };
 
    // Calculates the length of array
    int N = a.length;
     
    for(int i = 0; i < tree.length; i++)
        tree[i] = new Node();
         
    // Calls the build function to build
    // the segment tree
    build(a, 0, 0, N - 1);
 
    // Find the max digit-sum value between
    // 0th and 3rd index of array
    System.out.print(
        query(0, 0, N - 1, 0, 3).value + "\n");
 
    // Find the max digit-sum value between
    // 0th and 2nd index of array
    System.out.print(
        query(0, 0, N - 1, 0, 2).value + "\n");
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program to find
# maximum digit sum value
  
# Struct two store two values in one node
class Node:
     
    def __init__(self):
         
        self.value = 0
        self.max_digit_sum = 0
     
tree = [Node() for i in range(4 * 10000)]
 
# Function to find the digit sum
# for a number
def digitSum(x):
     
    sum = 0;
    while(x != 0):
        sum += (x % 10)
        x //= 10
         
    return sum
     
# Function to build the segment tree
def build(a, index, beg, end):
     
    if (beg == end):
  
        # If there is one element in array,
        tree[index].value = a[beg]
        tree[index].max_digit_sum = digitSum(a[beg])
     
    else:
        mid = (beg + end) // 2
  
        # If there are more than one elements,
        # then recur for left and right subtrees
        build(a, 2 * index + 1, beg, mid)
        build(a, 2 * index + 2, mid + 1, end)
         
        if (tree[2 * index + 1].max_digit_sum >
            tree[2 * index + 2].max_digit_sum):
         
            tree[index].max_digit_sum = tree[2 * index + 1].max_digit_sum
            tree[index].value = tree[2 * index + 1].value
         
        elif (tree[2 * index + 2].max_digit_sum >
              tree[2 * index + 1].max_digit_sum):
         
            tree[index].max_digit_sum = tree[2 * index + 2].max_digit_sum
            tree[index].value = tree[2 * index + 2].value
         
        else:
            tree[index].max_digit_sum = tree[2 * index + 2].max_digit_sum
            tree[index].value = max(tree[2 * index + 2].value,
                                    tree[2 * index + 1].value)
         
# Function to do the range query in the segment
# tree for the maximum digit sum
def query(index, beg, end, l, r):
 
    result = Node()
    result.value = result.max_digit_sum = -1
  
    # If segment of this node is outside the given
    # range, then return the minimum value.
    if (beg > r or end < l):
        return result
  
    # If segment of this node is a part of given
    # range, then return the node of the segment
    if (beg >= l and end <= r):
        return tree[index]
  
    mid = (beg + end) // 2
  
    # If left segment of this node falls out of
    # range, then recur in the right side of
    # the tree
    if (l > mid):
        return query(2 * index + 2, mid + 1, end, l, r)
  
    # If right segment of this node falls out of
    # range, then recur in the left side of
    # the tree
    if (r <= mid):
        return query(2 * index + 1, beg, mid, l, r)
  
    # If a part of this segment overlaps with
    # the given range
    left = query(2 * index + 1, beg, mid, l, r)
    right = query(2 * index + 2, mid + 1, end, l, r)
  
    if (left.max_digit_sum > right.max_digit_sum):
        result.max_digit_sum = left.max_digit_sum
        result.value = left.value
     
    elif (right.max_digit_sum > left.max_digit_sum):
        result.max_digit_sum = right.max_digit_sum
        result.value = right.value
     
    else:
        result.max_digit_sum = left.max_digit_sum
        result.value = max(right.value, left.value)
  
    # Returns the value
    return result
     
# Driver code
if __name__=="__main__":
     
    a = [ 16, 12, 43, 55 ]
  
    # Calculates the length of array
    N = len(a)
  
    # Calls the build function to build
    # the segment tree
    build(a, 0, 0, N - 1)
  
    # Find the max digit-sum value between
    # 0th and 3rd index of array
    print(query(0, 0, N - 1, 0, 3).value)
  
    # Find the max digit-sum value between
    # 0th and 2nd index of array
    print(query(0, 0, N - 1, 0, 2).value)
    
# This code is contributed by rutvik_56

// C# program to find
// maximum digit sum value
using System;
class GFG{
 
// Struct two store
// two values in one node
class Node
{
  public int value;
  public int max_digit_sum;
};
 
static Node []tree = new Node[4 * 10000];
 
// Function to find the digit sum
// for a number
static int digitSum(int x)
{
  int sum = 0;
 
  while (x > 0)
  {
    sum += (x % 10);
    x /= 10;
  }
  return sum;
}
 
// Function to build the segment tree
static void build(int []a, int index,
                  int beg, int end)
{
  if (beg == end)
  {
    // If there is one element in array,
    tree[index].value = a[beg];
    tree[index].max_digit_sum =
                digitSum(a[beg]);
  }
  else
  {
    int mid = (beg + end) / 2;
 
    // If there are more than one elements,
    // then recur for left and right subtrees
    build(a, 2 * index + 1, beg, mid);
    build(a, 2 * index + 2, mid + 1, end);
 
    if (tree[2 * index + 1].max_digit_sum >
        tree[2 * index + 2].max_digit_sum)
    {
      tree[index].max_digit_sum =
           tree[2 * index + 1].max_digit_sum;
      tree[index].value =
           tree[2 * index + 1].value;
    }
    else if (tree[2 * index + 2].max_digit_sum >
             tree[2 * index + 1].max_digit_sum)
    {
      tree[index].max_digit_sum =
           tree[2 * index + 2].max_digit_sum;
      tree[index].value =
           tree[2 * index + 2].value;
    }
    else
    {
      tree[index].max_digit_sum =
           tree[2 * index + 2].max_digit_sum;
      tree[index].value =
           Math.Max(tree[2 * index + 2].value,
                tree[2 * index + 1].value);
    }
  }
}
 
// Function to do the range query
// in the segment tree for the
// maximum digit sum
static Node query(int index, int beg,
                  int end, int l, int r)
{
  Node result = new Node();
  result.value = result.max_digit_sum = -1;
 
  // If segment of this node is
  // outside the given range,
  // then return the minimum value.
  if (beg > r || end < l)
    return result;
 
  // If segment of this node
  // is a part of given range,
  // then return the node of the segment
  if (beg >= l && end <= r)
    return tree[index];
 
  int mid = (beg + end) / 2;
 
  // If left segment of this
  // node falls out of range,
  // then recur in the right
  // side of the tree
  if (l > mid)
    return query(2 * index + 2, mid + 1,
                 end, l, r);
 
  // If right segment of this
  // node falls out of range,
  // then recur in the left side of
  // the tree
  if (r <= mid)
    return query(2 * index + 1, beg,
                 mid, l, r);
 
  // If a part of this segment
  // overlaps with the given range
  Node left = query(2 * index + 1, beg,
                    mid, l, r);
  Node right = query(2 * index + 2, mid + 1,
                     end, l, r);
 
  if (left.max_digit_sum > right.max_digit_sum)
  {
    result.max_digit_sum = left.max_digit_sum;
    result.value = left.value;
  }
  else if (right.max_digit_sum > left.max_digit_sum)
  {
    result.max_digit_sum = right.max_digit_sum;
    result.value = right.value;
  }
  else
  {
    result.max_digit_sum = left.max_digit_sum;
    result.value = Math.Max(right.value,
                            left.value);
  }
 
  // Returns the value
  return result;
}
 
// Driver code
public static void Main(String[] args)
{
  int []a = {16, 12, 43, 55};
 
  // Calculates the length
  // of array
  int N = a.Length;
 
  for(int i = 0; i < tree.Length; i++)
    tree[i] = new Node();
 
  // Calls the build function
  // to build the segment tree
  build(a, 0, 0, N - 1);
 
  // Find the max digit-sum value between
  // 0th and 3rd index of array
  Console.Write(query(0, 0,
                      N - 1,
                      0, 3).value + "\n");
 
  // Find the max digit-sum value between
  // 0th and 2nd index of array
  Console.Write(query(0, 0,
                      N - 1,
                      0, 2).value + "\n");
}
}
 
// This code is contributed by Rajput-Ji

<script>
    // Javascript program to find maximum digit sum value
     
    // Struct two store two values in one node
    class Node
    {
        constructor() {
           this.value = 0;
           this.max_digit_sum = 0;
        }
    }
     
    let tree = new Array(4 * 10000);
     
    // Function to find the digit sum for a number
    function digitSum(x)
    {
      let sum = 0;
 
      while (x > 0)
      {
        sum += (x % 10);
        x = parseInt(x / 10, 10);
      }
      return sum;
    }
 
    // Function to build the segment tree
    function build(a, index, beg, end)
    {
      if (beg == end)
      {
        // If there is one element in array,
        tree[index].value = a[beg];
        tree[index].max_digit_sum = digitSum(a[beg]);
      }
      else
      {
        let mid = parseInt((beg + end) / 2, 10);
 
        // If there are more than one elements,
        // then recur for left and right subtrees
        build(a, 2 * index + 1, beg, mid);
        build(a, 2 * index + 2, mid + 1, end);
 
        if (tree[2 * index + 1].max_digit_sum >
            tree[2 * index + 2].max_digit_sum)
        {
          tree[index].max_digit_sum =
               tree[2 * index + 1].max_digit_sum;
          tree[index].value =
               tree[2 * index + 1].value;
        }
        else if (tree[2 * index + 2].max_digit_sum >
                 tree[2 * index + 1].max_digit_sum)
        {
          tree[index].max_digit_sum =
               tree[2 * index + 2].max_digit_sum;
          tree[index].value =
               tree[2 * index + 2].value;
        }
        else
        {
          tree[index].max_digit_sum =
               tree[2 * index + 2].max_digit_sum;
          tree[index].value =
               Math.max(tree[2 * index + 2].value,
                    tree[2 * index + 1].value);
        }
      }
    }
 
    // Function to do the range query
    // in the segment tree for the
    // maximum digit sum
    function query(index, beg, end, l, r)
    {
      let result = new Node();
      result.value = result.max_digit_sum = -1;
 
      // If segment of this node is
      // outside the given range,
      // then return the minimum value.
      if (beg > r || end < l)
        return result;
 
      // If segment of this node
      // is a part of given range,
      // then return the node of the segment
      if (beg >= l && end <= r)
        return tree[index];
 
      let mid = parseInt((beg + end) / 2, 10);
 
      // If left segment of this
      // node falls out of range,
      // then recur in the right
      // side of the tree
      if (l > mid)
        return query(2 * index + 2, mid + 1, end, l, r);
 
      // If right segment of this
      // node falls out of range,
      // then recur in the left side of
      // the tree
      if (r <= mid)
        return query(2 * index + 1, beg, mid, l, r);
 
      // If a part of this segment
      // overlaps with the given range
      let left = query(2 * index + 1, beg,
                        mid, l, r);
      let right = query(2 * index + 2, mid + 1,
                         end, l, r);
 
      if (left.max_digit_sum > right.max_digit_sum)
      {
        result.max_digit_sum = left.max_digit_sum;
        result.value = left.value;
      }
      else if (right.max_digit_sum > left.max_digit_sum)
      {
        result.max_digit_sum = right.max_digit_sum;
        result.value = right.value;
      }
      else
      {
        result.max_digit_sum = left.max_digit_sum;
        result.value = Math.max(right.value, left.value);
      }
 
      // Returns the value
      return result;
    }
     
    let a = [16, 12, 43, 55];
  
    // Calculates the length
    // of array
    let N = a.length;
 
    for(let i = 0; i < tree.length; i++)
      tree[i] = new Node();
 
    // Calls the build function
    // to build the segment tree
    build(a, 0, 0, N - 1);
 
    // Find the max digit-sum value between
    // 0th and 3rd index of array
    document.write(query(0, 0,
                        N - 1,
                        0, 3).value + "</br>");
 
    // Find the max digit-sum value between
    // 0th and 2nd index of array
    document.write(query(0, 0,
                        N - 1,
                        0, 2).value + "</br>");
 
// This code is contributed by divyeshrabadiya07.
</script>

55
43

Análisis de Complejidad: 
La Complejidad de Tiempo para la construcción del árbol es O(N). Hay un total de 2n-1 Nodes, y el valor de cada Node se calcula solo una vez en la construcción del árbol.
La complejidad del tiempo para cada consulta es O (log N).
La complejidad temporal del problema es O(Q * log N)