algorithm - Multiplicación en un rango

data-structures tree

Question

Tengo una matriz de 10 números supra A [10] = {1,2,3,4,5,6,7,8,9,10} y tengo que calcular la multiplicación de números en un rango particular pero no obtener respuesta correcta, estoy usando el árbol de segmentos y no sé cómo usar la operación de consulta. Aquí está mi código:

#include<stdio.h>
#define m 1000000000
#define MAX 100010

typedef unsigned long long ull;
ull a[MAX];
ull tree[4*MAX];

void build_tree(int n,int b,int e){
    if(b>e)return ;
    else if(b==e){
        tree[n] = a[b];
        return ;
    }
    build_tree(n*2,b,(b+e)/2);
    build_tree(n*2+1,(b+e)/2+1,e);
    tree[n] =( tree[n*2]%m * tree[n*2 + 1]%m )%m;
}


ull query(int index, int ss, int se, int qs, int qe)
  {
      ull p1, p2,p;
      if (qs > se || qe < ss)
          return -1;

      if (ss >= qs && se <= qe)
          return tree[index];
      p1 = query(2 * index, ss, (ss + se) / 2, qs, qe);
      p2 = query(2 * index + 1, (ss + se) / 2 + 1, se,qs, qe);
      printf("/np1 = %d   p2 = %d",p1,p2);
      p=(tree[p1]%m*tree[p2]%m)%m;
      return p;

}
int main(){
    int n,i,query_start,query_end,segment_start,segment_end,index;
    ull value;
    scanf("%d",&n);
    for(i=0;i<n;i++)
       scanf("%lld",&a[i]);
    build_tree(1,0,n-1);
    query_start=1;
    query_end=2;
    segment_start=0;
    segment_end = n-1;
    index=1;
    printf("Tree Formed :-/n");
    for(i=0;i<n*4;i++)
          printf("%d  ",tree[i]);
    printf("/n/n");
    value=query(index,segment_start,segment_end,query_start,query_end);
    printf("/nvalue = %lld/n",value);
    return 0;
}

Answer 1

Esto está ligeramente fuera de tema, pero publicar esto principalmente como una respuesta a sasha sami. Esto todavía funciona como una idea alternativa para resolver el problema del OP.

Si no hay consultas, realmente no necesitamos usar un árbol de segmentos. La idea es mantener otra matriz que contenga los productos acumulativos de los valores en la matriz de entrada.

Entonces, si la matriz de entrada es

[1,2,3,4,5,6,7,8,9,10]

El conjunto de productos correspondiente será:

[1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]

Ahora, sabemos el producto de todos los elementos [0, i] para cualquier índice i. Para obtener el producto entre los índices i y j, podemos obtener el producto para [0, j] y [0, i] y usarlo para obtener nuestra respuesta. El producto para [i, j] es en realidad [0, j] / [0, i - 1]. Para evitar manejar especialmente el caso donde i = 0 también podemos reescribirlo como elemento [0, j] / [0, i] * en i.

Código (en Python):

#! /usr/bin/python


def build_products_array(array):
  ret = [0 for i in xrange(len(array))]
  ret[0] = array[0]
  last_value = 1 if array[0] else array[0]
  for i in xrange(1, len(array)):
    if array[i]:
      ret[i] = last_value * array[i]
      last_value = ret[i]
    else:
      ret[i] = last_value
  return ret


def build_zero_array(array):
  ret = [0 for i in xrange(len(array))]
  ret[0] = 0 if array[i] else 1
  for i in xrange(1, len(array)):
    ret[i] = ret[i - 1] + (0 if array[i] else 1)
  return ret


def check_zeros(zero_array, array, i, j):
  return zero_array[j] - zero_array[i] + (0 if array[i] else 1)


def query(products, zero_array, array, start, end):
  if check_zeros(zero_array, array, start, end):
    return 0
  else:
    return products[end] / products[start] * array[start]


def main():
  array = [1, 2, 3, 4, 5, 0, 7, 8, 9, 10]
  products = build_products_array(array)
  zeros = build_zero_array(array)
  for i in xrange(len(array)):
    for j in xrange(i, len(array)):
      print "Querying [%d, %d]: %d/n" % (i, j, query(products, zeros, array, i, j))


if __name__ == ''__main__'':
  main()

Lo que hay que tener en cuenta es el desbordamiento porque los productos acumulativos pueden ser bastante grandes, incluso si se garantiza que las respuestas a las consultas sean lo suficientemente pequeñas. Lo anterior lo codifica en Python, por lo que no hay temor de desbordamientos allí, pero en C ++ es posible que desee utilizar bignums. También es útil si necesita encontrar el número de módulo de productos, en cuyo caso el desbordamiento no es un problema.

Este enfoque también funcionará para encontrar la suma de un rango de números, o cualquier operación para la que también exista una operación inversa (por ejemplo, para suma, el inverso es resta, para productos el inverso es división). No funcionaría para operaciones como max o min.

Esto toma O (n) para construir la matriz de producto inicial, y cada consulta es O (1). Entonces esto es más rápido que el árbol de segmentos (que consulta en O (log n)).

EDITAR: actualizó el código para manejar ceros en la entrada. Mantenemos otra matriz manteniendo la cuenta total de 0 en cada índice. Para cada consulta, verificamos esa matriz para ver si hay ceros en ese rango (como antes, conociendo el recuento de [0, i] y [0, j], podemos calcular el recuento de [i, j]) ) Si los hay, la respuesta a esa consulta debe ser 0. De lo contrario, devolvemos el producto.

Answer 2

Yo uso la siguiente plantilla para el árbol de segmento es general:

/*The query function to get maximum in a range*/
function get_max(cur_node, i, j) {
i = max(i, cur_node.i)
j = min(j, cur_node.j)
if (i > j) return -infinity
if (i == cur_node.i and j == cur_node.j) return cur_node.max
res = max(get_max(cur_node.left_child, i, j), get_max(cur_node.right_child, i, j))
res += cur_node.add
return res
}

/* update function which you don''t need in this case*/
function update(cur_node, i, j, a) {
i = max(i, cur_node.i)
j = min(j, cur_node.j)
if (i > j) return
if (i == cur_node.i and j == cur_node.j) {
  cur_node.add += a
  cur_node.max += a
  return
}
update(cur_node.left_child, i, j, a)
update(cur_node.right_child, i, j, a)
cur_node.max = max(cur_node.left_child.max, cur_node.right_child.max) + cur_node.add
}

Answer 3

para la multiplicación en un rango de consulta utilizando árbol de segmentos, debe ''devolver 1'' en la condición if(b>e) dentro del método build_tree Y también en el if (qs > se || qe < ss) dentro del método de ull query Y agregue algunas condiciones como abajo en su caso.

int build_tree(int n,int b,int e){
    if(b>e)return 1;
    else if(b==e){
        tree[n] = a[b];
        return tree[n];
    }
    build_tree(n*2,b,(b+e)/2);
    build_tree(n*2+1,(b+e)/2+1,e);
    tree[n] =( tree[n*2]%m * tree[n*2 + 1]%m )%m;
}


ull query(int index, int ss, int se, int qs, int qe)
  {
      ull p1, p2,p;
      if (qs<= ss && qe>= se)
        {
            return tree[index];
        }
      if (qs > se || qe < ss)
          return 1;

      if (ss >= qs && se <= qe)
          return tree[index];
      p1 = query(2 * index, ss, (ss + se) / 2, qs, qe);
      p2 = query(2 * index + 1, (ss + se) / 2 + 1, se,qs, qe);
      printf("/np1 = %d   p2 = %d",p1,p2);
      p=(tree[p1]%m*tree[p2]%m)%m;
      return p;

}

Gracias.

Answer 4

if (qs > se || qe < ss)
      return -1;

Hay un error en la instrucción if utilizada en el código. La función debería devolver 1 en lugar de -1 si se produce la condición anterior. El resto de la función de consulta parece estar bien.