algorithm - الضرب في نطاق




data-structures tree (3)

لدي صفيف إلى 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;
}

أستخدم القالب التالي لشجرة الشريحة عامة:

/*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
}

بالنسبة إلى الضرب في نطاق الاستعلام باستخدام شجرة الشرائح، يجب عليك "إرجاع 1" في حالة build_tree if(b>e) داخل أسلوب build_tree وأيضا في build_tree if (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;

}

شكر.


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

هناك خطأ في بيان إف المستخدمة في التعليمات البرمجية. يجب أن ترجع الدالة 1 بدلا من -1 إذا ظهرت الحالة أعلاه. بقية وظيفة الاستعلام تبدو على ما يرام.