Multiplication in a range

Question

I have an array to 10 numbers supprse A[10] = {1,2,3,4,5,6,7,8,9,10} and I have to compute the multiplication of numbers in a particular range but not getting correct answer, I am using segment tree and dont know how to use query operation Here is my code :

#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

This is slightly off topic, but posting this mainly as a response to sasha sami. This still works as an alternate idea to solve the OP's problem.

If there are no queries, we don't really need to use a segment tree. The idea is to keep another array containing the cumulative products of the values in the input array.

So, if the input array is

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

The corresponding product array will be:

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

Now, we know the product of all elements [0, i] for any index i. To get the product between indices i and j, we can just get the product for [0, j] and [0, i] and use that to get our answer. The product for [i, j] is actually [0, j] / [0, i - 1]. To avoid specially handling the case where i = 0 we can also rewrite it as [0, j] / [0, i] * element at i.

Code (in 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()

The thing to watch out for is overflows because the cumulative products can get quite big, even if the answers to the queries are guaranteed to be small enough. The above code it in Python, so there's not fear of overflows there, but in C++ you might want to use bignums. Its also handy if you need to find the products modulo some number - in which case overflow is not an issue.

This approach will also work for finding the sum of a range of numbers, or any operation for which an inverse operation also exists (e.g. for sum the inverse is subtraction, for products the inverse is division). It wouldn't work for operations like max or min.

This takes O(n) to build the initial product array, and each query is O(1). So this is actually faster than segment tree (which queries in O(log n) ).

EDIT: Updated the code to handle zeros in the input. We keep another array keeping the total count of 0s at each index. For each query we check that array to see if there are any zeros in that range (as before, knowing the count for [0, i] and [0, j], we can figure out the count for [i, j])). If there are, the answer to that query must be 0. Otherwise we return the product.

Answer 2

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

There is a bug in the if statement used in the code. The function should return 1 instead of -1 if the above condition comes across. The rest of the query function seems fine.

Answer 3

I use the following template for segment tree its 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 4

for multiplication in a query range using segment tree, You have to 'return 1' in the if(b>e) condition inside the build_tree method AND also in the if (qs > se || qe < ss) inside the ull query method AND add some conditions as below in your case.

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;

}

Thanks.