Kurs maturalny z języka angielskiego!
kurs-maturalny-jezyk-angielski

PROGRAMOWANIE I ALGORYTMY

Zajęcia maturalne z informatyki
Olimpiada Informatyczna Juniorów
    Prowadzący: Marcin Kasprowicz
  • właściciel serwisu algorytm.edu.pl
  • wrzesień 2024 — start zajęć
  • czytaj więcej

Dynamiczne drzewo przedziałowe


Program realizuje dynamicznie rozwijalne drzewo przedziałowe zliczające elementy w przedziale. Złożoność wstawiania elementów wynosi O(log2 n), natomiast odpowiadanie na zapytanie wynosi O(log n).

#include<bits/stdc++.h>
#define ui unsigned int
#define gl 21 //głębokosć drzewa
int *maska;
 
struct wezly{
    ui w;
  wezly *left, *right, *top;
} *w;
 
void insert(ui x, ui val); //wstawianie elementów
ui query(ui a, ui b);    //odpowiadanie na zapytania
//======================================================
int main()
{
  maska = new int[gl+1];
  for(int i=0;i<=gl;i++)maska[i]=(1<<(gl-i-1));
  ui t, l, q, a, b;
 
 
  w = new wezly;
  w->left = w->right = w->top = NULL; w->w=0;
  //podanie ilosci elementów, które wrzucimy do drzewa
  scanf("%d %d",&t);
 
  while(t--)
  {
    //wczytanie elementu i wstawienie go do drzewa
    scanf("%d",&l);insert(l,1);
  }
  //podanie liczby zapytań
  scanf("%d",&q);
 
  while(q--)
  {
    //zapytanie z przedziału [a, b]
    scanf("%d %d",&a,&b);
    //generowanie wyniku
    printf("%d\n",query(a,b));
  }
  return 0;
}
//===================================================== 
void insert(ui x, ui val) {
 
   wezly *pom = w, *pom2, *pom3;  
   for(ui i=0;i<gl;i++)
   {
  //   printf("%d\n",v&maska[i]);
       if((x&maska[i])>0) //jeli różne od zera to idziemy w prawą stronę - gdy 1
       {
         if(pom->right==NULL) //tworzenie nowego elementu drzewa
         {
           pom2 = pom3 = pom;
        pom = new wezly; //tworzenie nowego węzła w drzewie
        pom->w=0;
           pom2->right = pom;
           pom2 = pom2->right; //zejscie o poziom nizej
           pom2->top = pom3; 
           pom = pom2;
           pom->right=pom->left=NULL;
         }
         else //element drzewa istnieje
           pom = pom->right;
       }
       else
       {
         if(pom->left==NULL)
         {
           pom2 = pom3 = pom;
        pom = new wezly; //tworzenie nowego węzła w drzewie
        pom->w=0;
           pom2->left = pom;
           pom2 = pom2->left; //zejscie o poziom nizej
           pom2->top = pom3;  //podpięcie poziomu wyżej
           pom = pom2; 
           pom->right=pom->left=NULL;
         }
         else
           pom = pom->left;
       }
   }
   //gdy jestem lisciem
   pom->w+= val; pom = pom ->top;
 
   while (pom != NULL) {
     pom->w=0;
     if(pom->left!=NULL)pom->w=pom->left->w;
     if(pom->right!=NULL)pom->w+=pom->right->w;
     //printf("%d\n",pom->w);
     pom = pom ->top;
   }
}
 
ui query(ui a, ui b) {
   ui i=0;
   wezly * pom = w, *pom2;
 
   while(pom!=NULL)
   {
 
       if((a&maska[i])!=(b&maska[i])){++i;if(i==gl){return ((pom->left!=NULL)?pom->left->w:0)
       +((pom->right!=NULL)?pom->right->w:0);}else break;}
 
    if((a&maska[i])>0)pom = pom->right; else pom=pom->left;
       ++i;
       if(i==gl)if(pom!=NULL)return pom->w;else return 0;
   }
 
 
   if(pom==NULL)return 0;
 
   int wyn = 0;
 
   pom2=pom;ui j=i;
 
   pom=pom->left;
   //szukanie prawych bombek
   while (pom!=NULL) {
       if((a&maska[i])==0)//gdy idę w lewo
       {
          if(pom->right!=NULL)
             wyn+=pom->right->w;
          pom = pom->left;
        }
    else pom=pom->right;
     ++i;
     if(i==gl)if(pom!=NULL)wyn+= pom->w;else break;
   }
 
   pom=pom2;i=j;
   pom=pom->right;
   //szukanie lewych bombek
   while (pom!=NULL) {
       if((b&maska[i])>0) //gdy idę w prawo
       {
          if(pom->left!=NULL) //sprawdzam czy istnieje lewa bombka
             wyn+=pom->left->w;
          pom = pom->right;
        }
    else pom=pom->left;
     ++i;
     if(i==gl)if(pom!=NULL)wyn+= pom->w;else break;
   }
 
   return wyn;
}