infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: cippi din Decembrie 08, 2005, 14:21:56

Titlul: Răspuns: 007 Arbori de intervale
Scris de: cippi din Decembrie 08, 2005, 14:21:56

Vreau sa stiu si eu cum se poate preprocesa acea structura pentru un vector in O(N)...asa cum zice in articolul LCA. :evil:

Titlul: Răspuns: 007 Arbori de intervale
Scris de: Vlad Berteanu din Decembrie 08, 2005, 15:43:36

Daca te referi la RMQ cu arbore de intervale..cred ca merge asa :

Cod:



 procedure build_tree(nod,st,dr:longint);
 var juma:longint;
 begin
 if st=dr then arb[nod]:=valoare[st]
  else
   begin
   juma:=(st+dr) div 2;
   build_tree(2*nod,st,juma);
   build_tree(2*nod+1,juma+1,dr);
   arb[nod]:=minim(arb[2*nod],arb[2*nod+1]);
   end;
 end;

Titlul: Răspuns: 007 Arbori de intervale
Scris de: cippi din Decembrie 08, 2005, 16:49:30

Da mai...ms..si cat m-am mai gandit :D