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++ では bignum を使用したい場合があります。また、ある数を法とする積を見つける必要がある場合にも便利です。この場合、オーバーフローは問題になりません。

このアプローチは、数値の範囲の合計、または逆演算も存在する演算 (たとえば、和の逆数は減算、積の逆数は除算) を求める場合にも機能します。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 に答える