在一个范围内的乘法

Question

我有一个数组到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;
}

Answer 1

这略微偏离主题,但主要是作为对sasha sami的回应.这仍然是解决OP问题的另一种想法.

如果没有查询,我们实际上不需要使用段树.我们的想法是保留另一个包含输入数组中值的累积产品的数组.

所以,如果输入数组是

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

相应的产品阵列将是:

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

现在,我们知道任何索引i的所有元素[0,i]的乘积.为了获得索引i和j之间的乘积,我们可以得到[0,j]和[0,i]的乘积并用它来得到我们的答案.[i,j]的乘积实际上是[0,j]/[0,i - 1].为了避免特别处理i = 0的情况,我们也可以在i处将其重写为[0,j]/[0,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.如果您需要找到以某些数字为模的产品,它也很方便 - 在这种情况下,溢出不是问题.

该方法还将用于找到一系列数字的总和,或者也存在逆操作的任何操作(例如,对于求逆的和,对于逆是除法的乘积).它不适用于max或min等操作.

这需要O(n)来构建初始产品数组,每个查询都是O(1).所以这实际上比段树(在O(log n)中查询)更快.

编辑:更新了代码以在输入中处理零.我们保留另一个数组,使每个索引的总计数为0.对于每个查询,我们检查该数组以查看该范围内是否有任何零(如前所述,知道[0,i]和[0,j]的计数,我们可以计算出[i,j]的计数) ).如果有,则该查询的答案必须为0.否则我们返回产品.