我有一个10个数字的数组suprse 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;
}
最佳答案
这个话题有点离题，但主要是为了回应萨沙·萨米这仍然可以作为解决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++中，你可能想使用BigNeg。如果你需要找到某个数的乘积模，它也很方便——在这种情况下，溢出不是问题。
这种方法也将用于寻找一系列数字的总和，或任何逆运算也存在的操作（例如，对于乘法求逆，求逆乘除）。它不适用于像max或min这样的操作。
这需要o（n）来构建初始产品数组，每个查询都是o（1）。所以这实际上比段树（在o（log n）中查询）更快。
编辑：
更新代码以处理输入中的零。我们保留另一个数组，使每个索引的总数为0。对于每个查询，我们检查该数组以查看该范围内是否有任何零（与之前一样，知道[0，i]和[0，j]的计数，我们可以计算出[i，j]的计数）。如果存在，则该查询的答案必须为0。否则我们就退货。
关于algorithm - 范围内的乘法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18029531/