Răspuns: 007 Arbori de intervale

[cippi]

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

[•vladcyb1]

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;

[cippi]

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