algorithm - 范围内的乘法

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]

现在，我们知道所有元素 [0, i] 对任何索引 i 的乘积。为了得到索引 i 和 j 之间的乘积，我们可以只得到 [0, j] 和 [0, i] 的乘积，然后用它来得到我们的答案。 [i, j] 的乘积实际上是 [0, j]/[0, i - 1]。为了避免特殊处理 i = 0 的情况，我们也可以将其重写为 [0, j]/[0, i] * element at 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。否则我们将退回产品。