2

我有一个包含 10 个数字的数组 supprse 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

4 回答 4

5

这有点偏离主题，但主要是作为对 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 的情况，我们还可以将其重写为 [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。如果您需要以某个数字为模找到产品，它也很方便 - 在这种情况下溢出不是问题。

这种方法也适用于查找一系列数字的总和，或任何逆运算也存在的运算（例如，求和的逆运算是减法，乘积的逆运算是除法）。它不适用于 max 或 min 之类的操作。

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

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

于 2013-08-03T11:57:19.903 回答
1 
if (qs > se || qe < ss)
      return -1;

代码中使用的 if 语句存在错误。如果遇到上述情况，该函数应返回 1 而不是 -1。查询功能的其余部分似乎很好。

于 2017-01-09T05:52:48.060 回答
0

我使用以下模板作为段树的一般模板：

/*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
}
于 2013-08-03T10:35:08.297 回答
0

对于使用段树在查询范围内进行乘法运算，您必须在方法内部的条件中以及在方法内部 的if(b>e)条件中“返回 1”，并在您的情况下添加一些条件，如下所示。build_treeif (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;

}

谢谢。

于 2017-07-25T12:50:22.803 回答