Умножение в диапазоне

У меня есть массив до 10 чисел, за исключением A[10] = {1,2,3,4,5,6,7,8,9,10}, и я должен вычислить умножение чисел в определенном диапазоне, но не получаю правильный ответ, я использую дерево сегментов и не знаю, как использовать операцию запроса Вот мой код:

#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;
}
Источник

4 ответа

Решение

Это немного не по теме, но публикуем это в основном как ответ sasha sami. Это все еще работает как альтернативная идея для решения проблемы ОП.

Если запросов нет, нам не нужно использовать дерево сегментов. Идея состоит в том, чтобы сохранить другой массив, содержащий совокупные произведения значений во входном массиве.

Итак, если входной массив

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

Соответствующий массив продуктов будет:

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

Теперь мы знаем произведение всех элементов [0, i] для любого индекса i. Чтобы получить произведение между индексами i и j, мы можем просто получить произведение для [0, j] и [0, i] и использовать его, чтобы получить наш ответ. Произведение для [i, j] фактически равно [0, j] / [0, i - 1]. Чтобы избежать специальной обработки случая, когда i = 0, мы также можем переписать его как элемент [0, j] / [0, i] * в i.

Код (в 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()

Остерегайтесь переполнения, потому что накопленные продукты могут быть довольно большими, даже если ответы на запросы гарантированно будут достаточно маленькими. Приведенный выше код написан на Python, поэтому здесь нет страха перед переполнением, но в C++ вы можете использовать bignums. Это также удобно, если вам нужно найти продукты по модулю некоторого числа - в этом случае переполнение не является проблемой.

Этот подход также будет работать для нахождения суммы диапазона чисел или любой операции, для которой также существует обратная операция (например, для суммы обратное вычитание, для продуктов обратное деление). Это не будет работать для таких операций, как макс или мин.

Для построения исходного массива продуктов требуется O(n), а каждый запрос - O(1). Так что это на самом деле быстрее, чем дерево сегментов (которое запрашивает в O(log n)).

РЕДАКТИРОВАТЬ: Обновлен код для обработки нулей на входе. Мы сохраняем другой массив, сохраняя общее число 0 для каждого индекса. Для каждого запроса мы проверяем этот массив, чтобы увидеть, есть ли какие-либо нули в этом диапазоне (как и раньше, зная количество для [0, i] и [0, j], мы можем вычислить количество для [i, j])). Если есть, ответ на этот запрос должен быть 0. В противном случае мы возвращаем продукт.

Источник 
if (qs > se || qe < ss)
      return -1;

В операторе if, используемом в коде, есть ошибка. Функция должна возвращать 1 вместо -1, если встречается указанное выше условие. Остальная часть функции запроса выглядит нормально.

Источник

Я использую следующий шаблон для дерева сегментов:

/*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
}
Источник

Для умножения в диапазоне запросов с использованием дерева сегментов, вы должны "вернуть 1" в if(b>e) состояние внутри build_tree метод И также в if (qs > se || qe < ss) внутри ull query метод И добавить некоторые условия, как показано ниже в вашем случае.

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;

}

Благодарю.

Источник
Другие вопросы по тегам